作业|学习资料|算法|题解

程序设计-寒假作业3052

凝神长老 · 1月19日 · 2017年 615次已读

本文写于 2017年01月19日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


程序设计-寒假作业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三稿

本题另有两种解法,参见:

0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论