Visits: 176

程序设计-寒假作业3052

本题另有2种解法，参阅《程序设计-寒假作业3052再解》、《程序设计-寒假作业3052又解》。

Description

如果一个整数用十进制表示时，不存在连续两位相同，则称之为“不重复数”。例如，105 、1234 和12121 都是“不重复数”，而11 、100 和1225 不是“不重复数”。
给定一个十进制正整数A ，返回大于A 的最小“不重复数”。

Input

第1行：一个整数T（1≤T≤10）为问题数。
第2~T+1行，每行一组测试数据，包括一个正整数A (1≤A≤10100)。

Output

对每个测试数据，首先输出一行问题的编号（0开始编号，格式：case #0: 等）。在接下来一行中输出大于A的最小不重复数。

Sample Input

3
2
99999999999
679898

Sample Output

case #0:
3
case #1:
101010101010
case #2:
680101

最原始的一种做法，大概就是，拿到一个数字，加1，看看是不是我的目标，是，输出，不是，再加1，看看是不是我的目标……

遗憾的是，这种方法似乎是超时的？（注：未经仔细测试，只是用这种方法写了简单的程序试了一下是否会超时，或许程序本身有误也未可知）

那么，还有一种办法，也容易想到，那就是从右往左依次检查（注意是从右往左），如果遇到连续两个相同的，就需要在这里加1，而没有从原来的数字最后一位开始加1。

比如，1233987，显然33是重复的，所以需要在第2个3那里加1，变成34，即1234987。

需要注意的是，这样是错的，我就曾在这个地方错误过，理由是，比1233987大的最小不重复数未必比1234987大。

1233987显然需要把33变成34，但是后面就应该从1234000开始尝试，最小的不重复数是1234010。

那么，就有了基本思路，把重复数33变成34，然后把后面的全部置为0。这时后面的0肯定都是重复了，不过不要紧，下一轮循环从右往左做，自然地去处理那部分0了。

接着想一想怎么处理进位。

由于每次只加1，所以只可能在9上面产生进位，所以只要这一位是9，就让它变成0，然后前一位继续加1。

那如果是999这样的数怎么办，进位以后会变成1000，多了一位。

这时候可以在循环里面加一个判断条件，如果最高位是9，把它变成0，然后每一位往右移动，移动后的最高位置为1。

在这里移动的过程中，涉及到字符串结束符的处理，这个处理顺序是有讲究的，下文会详述。

由上面的分析，我们逐步把程序写出来。

int main() {
    int cas;
    scanf ( "%d", &cas );

    for ( int t = 0; t < cas; t++ ) {
        printf ( "case #%d:\n", t );
        char st[1000];
        scanf ( "%s", st );
        solve ( st );
    }

    return 0;
}

主程序很简单，每次读入一个st，然后调用solve()去处理就好了。

void solve ( char st[] ) {

    int cur = strlen ( st ) - 1;

    do {
        add ( st, cur );
        cur = isNotTarget ( st );
    } while ( cur );

    printf ( "%s\n", st );
}

因为需要输出的数字必须必输入的数字大，所以add()至少要做一次，用do…while循环。

上面的分析说到，每次加1，应该是加在重复数字那里，可是，最开始的时候，不知道重复数字在哪里，怎么办？

一种解决方法是，先判断一下重复在哪里，然后把cur变成那一位，调用add()。

我这里采用了更加简单的方法，直接在最后一位加1，也就是在strlen(st)-1那一位上加1。注意strlen(st)要减1。

do…while循环里面，就是在st字符串的第cur位上加1，然后判断是不是不重复数。加1调用的是add()，判断调用的是isNotTarget()。

先说说isNotTarget()。

上面分析说到，从右往左依次检查，如果遇到连续两个相同的，那么这就不是不重复数，也就是isNotTarget为true。

同样地，思路与《程序设计-寒假作业3058》一样，这个isNotTarget()只需要0或者1就行了（即只需要true或者false），不过，反正遍历的时候需要一个cur，那么就干脆让它再多做一点事情，当不是不重复数的时候，顺便把重复的那位一起给返回出来。

这么做需要考虑0这个情况，因为0，到底是说，这是一个不重复数（isNotTarget==false），还是说在第0位上有重复？显然，我们需要返回的重复位置，一定是靠右的，那么下标为0作为最高位，不可能是重复那一位，所以这么做没有问题。

int isNotTarget ( char st[] ) {
    int ret = 0;

    for ( int i = strlen ( st ) - 2; i >= 0; i-- ) {
        if ( st[i] == st[i + 1] ) {
            ret = i + 1;
        }
    }

    return ret;
}

isNotTarget()写好了，就剩下一个add()。

上文说到，最右位重复的数字加1，再右边的全部置为0，所以一开始进入add()，就可以把右边全部置为0。

for (int i =cur+1;i<strlen(st);i++){
        st[i]='0';
    }

然后在cur位上加1，这里的解决方法是，如果这一位是9，并且不是最高位，那么就循环执行循环体，把这一位变成0，再看看前一位。这个while循环可以处理掉进位，包括连续进位。

while ( st[cur] == '9' && cur > 0 ) {
        st[cur] = '0';
        cur--;
    }

循环退出的条件只有2种，要么这一位是最左边一位，要么这一位不是9。

if ( st[cur] != '9' ) {
        st[cur]++;

    } else {

如果这一位不是9，很简单，不论是不是最左边那位，直接加1就好。

否则的话，说明这是最高位，并且最高位还是9，这时就要处理移动字符串了。

st[cur] = '0';

st[strlen ( st ) + 1] = '\0';

for ( int i = strlen ( st ); i > 0; i-- ) {
        st[i] = st[i - 1];
}

st[0] = '1';

由于这一位还是要变成0的，所以别忘了在移动之前先把cur这一位变成0，即

st[cur] = '0';

接着是移动字符串，首先，让当前strlen(st)+1那一位变成字符串结束符，即

st[strlen ( st ) + 1] = '\0';

然后从strlen(st)那一位开始，每次把它左边那一位移动到这一位上面，即

for ( int i = strlen ( st ); i > 0; i-- ) {
        st[i] = st[i - 1];
}

最后把最高位置为1，即

st[0] = '1';

上文说到，处理字符串结束符的顺序很关键。

这里需要在for循环之前处理掉字符串结束符，而不能在最后处理，因为for循环会把strlen(st)这一位的字符串结束符替换成strlen(st)-1这一位的数字，因此for循环后面再用strlen(st)就会没法正确得到字符串结束符在哪里，而不用strlen(st)要想找到最后一位是很麻烦的。

因此，完整的add()函数就是：

void add ( char st[], int cur ) {
    for (int i =cur+1;i<strlen(st);i++){
        st[i]='0';
    }

    while ( st[cur] == '9' && cur > 0 ) {
        st[cur] = '0';
        cur--;
    }

    if ( st[cur] != '9' ) {
        st[cur]++;

    } else {
        st[cur] = '0';
        st[strlen ( st ) + 1] = '\0';

        for ( int i = strlen ( st ); i > 0; i-- ) {
            st[i] = st[i - 1];
        }

        st[0] = '1';
    }
}

至此，这个程序需要用到的所有函数都已经讲清楚了。

完整程序略。

2017-01-19_15-43一稿

2017-02-06_16-24二稿

2017-02-09_17-29三稿