
程序设计-寒假作业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三稿
本题另有两种解法,参见: