
如果一个数字有多组重复,那么最左边的那组重复,是肯定要被处理掉的,也就是最左边两个重复的数字,一定会做一次加1,于是右边所有的数字都变成0。可是变成0之后,0本身成看重复数字,所以为了保证最小,应该把0变成0101的交替。
Skyrim 经过尝试,写出了他的代码,顺利通过OJ,详细可阅读他的题解:《程序设计-C语言程序设计基础-寒假作业3052再解》。
我发现,整个程序实际上可以进一步简化。
于是我也动手写了一份,经测试正确。
下面慢慢来说。
首先要从左往右找到重复的两个数,那就逐个字符比较,可以有一个last表示上一位,一个current表示当前位,last==current就说明有重复,否则,继续往下比较。
等等,如果是个位数,怎么办?
个位数没有办法弄出last和current。不过不要紧,个位数一定不会是重复的。
因此直接加1就可以输出。即使遇到9,需要进位,变成10,10也是正确的答案。
这样一来,思路就很清楚了。
if ( strlen ( st ) == 1 ) { } else { }
先来填个位数。
取出那一位,加1,输出。
为了方便进位,这里可以直接把字符变成数字,加1,那么数字9加1变成数字10,也就不需要处理进位了。
if ( strlen ( st ) == 1 ) { printf ( "%d" , st[0] - '0' + 1 ); } else { }
接着写else的部分。
pos是用来记录当前处在字符串的哪一个position,因为至少会有2个字符,所以st[1]必存在,pos直接初始化为1,last为st[0],current为st[1]。
pos = 1; last = st[pos - 1]; current = st[pos];
接着是比较。
if ( last == current ) { } else { }
如果last和current是一样的,就说明这是重复的数字,那么按照上文的分析,就应该把字符串从头到current之前照常输出、把current加1、把current之后的变成010101……
照常输出的部分比较简单。
for (int i=0;i<pos;i++){ printf("%c",st[i]); }
cuurent加1,就有可能产生进位,这里先不考虑进位。
printf("%c",st[pos]+1);
后面是输出010101……
循环的条件是容易控制的,就是从pos+1位一直到小于strlen。
关键是怎么控制0和1交替?
似曾相识?
有一个小技巧,在Pascal中比较常见。
这是因为Pascal有“前驱”和“后继”的概念,所以常用这种方法交换TRUE和FALSE。
一个整数p,做|p-1|,就可以完成0和1的交替。
比如p=1,p-1就是0,取绝对值,就是0,这时p=0,p-1就是-1,取绝对值就是1,这时p=1……如此循环往复。
由于要最小的不重复数,所以是0和1的交替,而不是1和0的交替,因此p从0开始。
int p = 0; for ( int i = pos + 1; i < strlen ( st ); i++ ) { printf ( "%d", p ); p = abs ( p - 1 ); }
如果是C语言,大概不会首先想到这种方法,而是会想到利用奇偶性,就是除以2取余数。
首先令cnt=strlen(st)-pos-1,然后for循环从0到小于cnt。
循环体输出i除以2的余数,即输出(“%d”,i%2)。
比如i为0,0%2=0,输出0,接着i为1,1%2=1,输出1,接着i为2,输出0……
printf ( "%d", i % 2 );
再不然。
if ( ( strlen ( c ) - i ) % 2 == 0 ) { for ( ; i < strlen ( c ); i += 2 ) { c[i] = '0'; c[i + 1] = '1'; } } else { c[i++] = '0'; for ( ; i < strlen ( c ); i += 2 ) { c[i] = '1'; c[i + 1] = '0'; } } }
到这里,last==current的事情就做完了。
if ( last == current ) { for ( int i = 0; i < pos; i++ ) { printf ( "%c", st[i] ); } printf ( "%c", st[pos] + 1 ); int p = 0; for ( int i = pos + 1; i < strlen ( st ); i++ ) { printf ( "%d", p ); p = abs ( p - 1 ); } } else {
如果不等,就要比较下一个。
于是pos就要加1,然后重新定last和current。
} else { pos++; last = st[pos - 1]; current = st[pos]; }
那pos加到什么时候结束?
比完整个字符串就结束,也就是说,外面还要套一层循环,终止的条件是pos==strlen。
pos = 1 ; last = st[pos - 1]; current = st[pos]; while ( pos < strlen ) { if ( last == current ) { } else { pos++; last = st[pos - 1]; current = st[pos]; } }
这时我们看到,last和current的赋值重复了,所以还可以进一步合并,以消除“代码复制”这一不良的做法。
除此以外,循环不仅由pos==strlen退出,还要可以提前break,这是因为我找到了最前面的那个重复数字,就可以输出正确答案,循环就到此为止了。
所以,在输出0101交替之后,要加上break。if ( strlen ( st ) == 1 ) {<br>printf ( "%d"st[0] - '0' + 1 );</p>
<p>} else {<br>pos = 1;</p>
<p><pre><code>while ( pos < strlen ) {<br>last = st[pos - 1];<br>current = st[pos];</p>
<p>if ( last == current ) {<br>for ( int i = 0; i < pos; i++ ) {<br>printf ( "%c", st[i] );<br>}</p>
<p>printf ( "%c", st[pos] + 1 );<br>int p = 0;</p>
<p>for ( int i = pos + 1; i < strlen ( st ); i++ ) {<br>printf ( "%d", p );<br>p = abs ( p - 1 );<br>}</p>
<p>break;</p>
<p>} else {<br>pos++;</p>
<p>}<br>}<br></code></pre></p>
<p>}
退出循环就产生了2种情况,如果pos==strlen,说明没有重复的,那么加1输出答案,如果pos!=strlen,说明已经发现重复数字,并且输出了结果,就不需要做什么了。
加1输出结果,意思是,从第0位到最后一位之前照抄,然后最后一位加1输出。(不考虑进位)if ( pos == strlen ( st ) ) {<br>for ( int i = 0; i < pos - 1; i++ ) {<br>printf ( "%c", st[i] );<br>}</p>
<p><pre><code>printf ( "%c", st[pos - 1] + 1 )<br></code></pre></p>
<p>}
到这里为止,我们把所有可能的情况都处理掉了,只剩下进位这件事。
进位是由加1引起的。
加1也是个大麻烦,因为会产生很多可能。
第一种是最令人放心的,加1,没有影响任何东西,比如34,加1,变成35,很好。
第二种是稍微复杂点的,就是进位。
进位又包括两种,一种是总位数不变,也就是需要进位的9不在最高位,比如39,进位变成40,另一种是需要进位的9在最高位,进位以后整个数字的位数增加,比如9,进位变成10,由1位数变成2位数。
第三种是最令人头疼的,就是加1以后产生新的重复数。
比如43,加1,变成44,又比如2199,加1,变成2200。
我们先来考虑pos==strlen这段代码里的进位。
其中第一种情况是最好处理的,上面的代码不用变。从第0位到最后一位之前照抄,然后最后一位加1输出。
pos==strlen的时候,第二种情况就被简化了。
因为对于9来说,个位数的9,加1,进位,变成10,而这一点在之前就已经被解决掉了,非个位数的9,那就是99、999之类的会有位数的变化,但是已经进入了pos==strlen,就不可能会有重复数字,因此这种情况也不需要考虑。
那么,对于类似19、39之类的,虽然有进位,不过也可以按照34+1=35这样操作。这时就不是“从第0位到最后一位之前照抄,然后最后一位加1输出”,而是“从第0位到最后第二位之前照抄,然后把最后两位当做整数,加1,输出”。
即,情况一和情况二,可以合并。
if ( pos == strlen ( st ) ) { for ( int i = 0; i < pos - 2; i++ ) { printf ( "%c", st[i] ); } int d; sscanf ( ( st + pos - 2 ), "%d", &d ); printf ( "%d", d + 1 ); }
这里运用到了sscanf(),之前没有接触过。
sscanf()和sprintf()是很强大的两个函数,尤其是当他们用「类似」正则表达式的格式控制符来输入和输出数据的时候。
如此强大的两个函数,想要掌握它们的全部功能,不是一时半会儿能解决的,因此这里只解释代码中用到的功能。
sscanf ( const char*, const char*, ... )
第一个参数,是读入数据的来源,来源要求是一个字符串。
因为我们想要从pos-2为开始读,有需要提供一个字符串,那么就可以用st+pos-2这种方法给一个字符串。
所以,第一个参数,我们写( st + pos – 2 )。
第二个参数,是格式控制符。
因为我们想要一个整数,是%d。
所以,第二个参数,我们写”%d”。
第三个参数开始,是读数据读到哪里,是一个地址,或者说,是一个基本数据类型的指针。
之前有了一个int d,那么这里就应该是&d,别忘了&。
所以,第三个参数,我们写&d。
简单说,这里用一个for循环输出到了pos-2之前,然后从pos-2这一位开始,把字符串以%d的形式,读入到一个int中,输出d+1。
第三种情况会产生新的重复数,所以在此之前,要把last==current那里遗留的进位问题处理掉。
也可以用类似的方法解决。for ( int i = 0; i < pos - 1; i++ ) {<br>printf ( "%c", st[i] );<br>}</p>
<p>int d;<br>sscanf ( ( st + pos - 1 ), "%d", &d );<br>printf ( "%d", d + 1 );<br>int p = 0;</p>
<p>for ( int i = pos + 1; i < strlen ( st ); i++ ) {<br>printf ( "%d", p );<br>p = abs ( p - 1 );<br>}
只是这里还要考虑99变成100、999变成1000的情况,即位数变化。
也就是要判断last是不是9。
如果last不是9,那么上面的代码就可以完成任务,如果last是9,那么last之前那一位(即pos-2)就要加1,而last开始变成0101循环。if ( last == '9' ) {<br>for ( int i = 0; i < pos - 2; i++ ) {<br>printf ( "%c", st[i] );<br>}</p>
<p><pre><code>printf ( "%c", st[pos - 2] + 1 );<br>int p = 0;</p>
<p>for ( int i = pos - 1; i < strlen ( st ); i++ ) {<br>printf ( "%d", p );<br>p = abs ( p - 1 );<br>}</p>
<p>break;<br></code></pre></p>
<p>} else {</p>
<p><pre><code>for ( int i = 0; i < pos - 1; i++ ) {<br>printf ( "%c", st[i] );<br>}</p>
<p>int d;<br>sscanf ( ( st + pos - 1 ), "%d", &d );<br>printf ( "%d", d + 1 );<br>int p = 0;</p>
<p>for ( int i = pos + 1; i < strlen ( st ); i++ ) {<br>printf ( "%d", p );<br>p = abs ( p - 1 );<br>}</p>
<p>break;<br></code></pre></p>
<p>}
写到pos-2的时候,要多一个心眼,那就是pos正好是最开头的两个数字怎么办?比如,11和99。
如果是11,pos是1,pos-1是0,由于for循环的循环条件是先验的,所以int i=0之后,i<0不成立,循环不执行,然后scanf()把11变成了整数11,加1输出12。
如果是99,似乎遇到了点麻烦,pos是1,pos-2是-1,for循环是不做了,却会遇到st[-1]这样的情况,下标越界了。
不妨加一个判断。
if ( pos - 2 >= 0 ) { printf ( "%c", st[pos - 2] + 1 ); } else { printf ( '1' ); }
然而
printf ( "%c", st[pos - 2] + 1 )
等语句就会产生上面所说的情况三,进位以后产生了新的重复数。
不论是pos==strlen还是last==current,都会产生新的重复数。
有没有可能避免掉这种情况?
比如,加2?
如果last比current大1,那么加1以后,就一定会有重复的数字,比如43,4比3大1,加1以后变成44就是重复的,因此加2。
不过,加2,似乎也没有办法解决掉所有的问题,比如,2199,加2,变成2201,显然也不满足要求。
如果last比current大1,并且last非9的时候,加2,是可以解决问题的。
一旦last和current是98,加1变成99,不行,加2变成100,既要处理进位,还可能使得进位后的数字与前面形成新的重复数,不行。
那判断是98的时候,加3行不行呢?加3仅仅处理掉了当前这个是不重复的,却不能保证进位以后还是不重复。比如2198,加1不行,加2不行,加3变成2201,保证了01不再重复,却使得22重复了。
于是,判断到98,还要去处理last前面的两位,也就是pos-3和pos-2,要判断st[pos-3]是不是比st[pos-2]大1。
万一98就是最前面的呢?万一这个数字就是98呢?
如果真的这样考虑下去,一定能做,分类总可以把所有的可能考虑完整。
但是,太麻烦了。
我们不想做麻烦的事。
因此,一种可能的操作方法是加一个循环,不断判断,直到没有重复数字为止。
这样一来,就不能在程序中直接输出了,而是要先把结果输出到一个ans的字符串中,判断ans没有问题,再输出。
于是,把上面所有的printf()改为输出到ans中。
个位数就不需要ans了,直接输出结果吧。
其他情况,就要首先有一个ans。
char ans[1000] = {0};
定义一个ans字符数组,初始化为0,这是为了方便后面用strlen判断应该输出到ans的哪一位。
输出部分用到了sprintf()。
sprintf ( char*, const char*, ... );
第一个参数,是输出到的字符串。
第二个参数,是格式控制符。
第三个参数开始,就是各种各样的变量。
举几个例子。
有一个char数组ans。
sprintf ( ans, "%d", 123 );
ans数组就是’1’、’2’、’3’。
sprintf ( ans, "%f", -1.23 );
ans数组就是’-‘、’1’、’.’、’2’、’3’。
为了方便书写和阅读,下面的例子就会写成ans=“123”、ans=“-1.23”。
sprintf ( ans, "%.5f", -1.23 );
ans=“-1.23000”
甚至可以直接变成16进制。
sprintf ( ans, "%d=%x", 123 + 456, 123 + 456 );
123+456是579,第1个579会以%d的形式输出到ans中,然后输出中间的等号,第2个579会以%x的形式输出到ans中。
得到的结果应该是“579=243”。
#include <stdio.h> int main() { char ans[100] = {0}; sprintf ( ans, "%d=%x", 123 + 456, 123 + 456 ); printf ( "%s\n", ans ); return 0; }
输出的结果是:
检验一下,确实如此:
更强大的功能暂时不说,但是就看上面几个例子,也能写出后面的代码了。
我们要把结果输出到ans中,那么就是ans。为了不让每次都从第0位开始覆盖,而是要不断往后写,这里就要指定ans开始的位置,需要开始写入的第一个位置恰好就是strlen(ans),这也就是之前要求把ans初始化为全0的原因,全部都是字符串结束符,就简化了操作。
因此,第一个参数,我们写( ans + strlen ( ans ) )。
sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );
把st的第i位,以%c的格式输出到ans的第strlen(ans)位,一开始strlen(ans)是0,正好就是ans开头,之后strlen(ans)变成1……
if ( pos - 2 >= 0 ) { sprintf ( ( ans + strlen ( ans ) ), "%c", st[pos - 2] + 1 ); } else { sprintf ( ( ans + strlen ( ans ) ), "%c", '1' ); }
这里的操作也是类似的,输出到ans的strlen(ans)位。
sprintf ( ( ans + strlen ( ans ) ), "%d", p );
这里输出的是整数,因此用的是%d,还是输出到ans的strlen(ans)位。
后面的操作类似,把所有的printf改成sprintf,输出到ans的第strlen位。
之后
if ( isTarget ( ans ) ) { printf ( "%s", ans ); } else { strcpy ( st, ans ); /** Again **/ }
因此,上面的代码可以继续嵌套在一个while循环里面,循环的终止条件是ans中没有重复数。
可是这样一来,进入while的时候可没有ans,而循环体显然至少执行一次,所以可以把while循环改成do…while循环。
do { if ( strlen ( st ) == 1 ) { } else { while ( pos < strlen ( st ) ) { if ( last == current ) { if ( last == '9' ) { } else { } } else { } if ( pos == strlen ( st ) ) { } } } } while ( !isTarget ( ans ) );
isTarget()也很好写。
int isTarget ( char* ans ) { for ( int i=1;i<strlen(ans);i++ ) { if ( ans[i] == ans[i - 1] ) { return 0; } } return 1; }
退出do…while循环的时候,输出ans。
再调整一下变量的初始化,比如把ans的定义拿到最外面,等等。
除了第1次进入do..while,之后每次进入do…while都需要把ans复制给st,并且清空ans。
(清空很重要,否则下一轮循环就没法用strlen(ans)判断输出到第几位了)
if ( strlen ( ans ) ) {
strcpy ( st, ans );
for ( int i = 0; i < strlen ( ans ); i++ ) {
ans[i] = 0;
}
}
补上多组输入输出。
补上换行符。
写换行符的时候,是这样处理的。
个位数依旧输出
<pre class="lang:c decode:true ">printf ( "%d", st[0] - '0' + 1 );</pre>
不加换行符。
退出do...while循环,依旧输出
<pre class="lang:c decode:true ">printf ( "%s", ans );</pre>
不加换行符。
这样一来,即便是个位数,退出do...while()循环,ans是空,不影响输出,之后再单独加上换行符。
当然,调整一下把个位数拿到do...while循环外面也是可以的。
试几组数据,发现100、1000出现问题了。
原因是00的重复,用%d变成了0,输出变成了1。因此,sprintf()那里,还不能只写%d,要写%02d。
<pre class="lang:c decode:true ">sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );</pre>
注意
<pre class="lang:c decode:true ">sprintf ( ( ans + strlen ( ans ) ), "%d", p );</pre>
不需要改动。
那
<pre class="lang:c decode:true ">sscanf ( ( st + pos - 2 ), "%d", &d );</pre>
有需要改成%02d吗?
也是有必要的。
比如,445,只要44,不需要445。
所以读入的时候,不是吧st+pos-2这个字符串当做整数读入,而是只读后面2位且把那2位当做整数。
全部改完之后,提交,AC。
但是,整个程序还可以进一步优化。
先给出至此为止的代码,后文进一步优化。
</code></pre>
<p>int isTarget ( char* ans ) {<br>for ( int i = 1; i < strlen ( ans ); i++ ) {<br>if ( ans[i] == ans[i - 1] ) {<br>return 0;<br>}<br>}<br>return 1;<br>}</p>
<p>int main () {<br>int cas;<br>scanf ( "%d", &cas );<br>for ( int t = 0; t < cas; t++ ) {<br>printf ( "case #%d:\n", t );<br>char st[1000] = {0};<br>scanf ( "%s", st );<br>char ans[1000] = {0};<br>do {<br>if ( strlen ( ans ) ) {<br>strcpy ( st, ans );<br>for ( int i = 0; i < strlen ( ans ); i++ ) {<br>ans[i] = 0;<br>}<br>}<br>if ( strlen ( st ) == 1 ) {<br>printf ( "%d", st[0] - '0' + 1 );<br>} else {<br>int pos = 1;<br>char last, current;<br>while ( pos < strlen ( st ) ) {<br>last = st[pos - 1];<br>current = st[pos];<br>if ( last == current ) {<br>if ( last == '9' ) {<br>for ( int i = 0; i < pos - 2; i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );<br>}<br>if ( pos - 2 >= 0 ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", st[pos - 2] + 1 );<br>} else {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", '1' );<br>}<br>int p = 0;<br>for ( int i = pos - 1; i < strlen ( st ); i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%d", p );<br>p = abs ( p - 1 );<br>}<br>break;<br>} else {<br>for ( int i = 0; i < pos - 1; i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );<br>}<br>int d;<br>sscanf ( ( st + pos - 1 ), "%02d", &d );<br>sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );<br>int p = 0;<br>for ( int i = pos + 1; i < strlen ( st ); i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%d", p );<br>p = abs ( p - 1 );<br>}<br>break;<br>}<br>} else {<br>pos++;<br>}<br>if ( pos == strlen ( st ) ) {<br>for ( int i = 0; i < pos - 2; i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );<br>}<br>int d;<br>sscanf ( ( st + pos - 2 ), "%02d", &d );<br>sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );<br>}<br>}<br>}<br>} while ( !isTarget ( ans ) );<br>printf ( "%s", ans );<br>printf ( "\n" );<br>}<br>return 0;<br>}<br>
优化,首先从消除代码复制开始。
我们看到循环输出0和1那部分,几乎是一模一样的代码。
因此,我们可以把它们提取出来,做一个printZeroAndOne()函数,函数接受的参数是begin和end的位数,或者也可以是输出多少位。
同样地,照抄pos之前的数字,也可以提取出来。
做一个printTheSame()。
void printTheSame ( int cnt, char* st, char * ans ) {<br>for ( int i = 0; i < cnt; i++ ) {<br>sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );<br>}<br>}</p>
<p>void printZeroAndOne ( int cnt, char* ans ) {</p>
<pre><code>int p = 0;
for ( int i = 0; i < cnt; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), "%d", p );
p = abs ( p - 1 );
}
</code></pre>
<p>}
中间进位的部分,各不相同,也没法做成一个函数。
到这里,整个程序已经很好了。
至此,整个程序已经很好了。
“代码复制”这一个大忌解决掉,剩下的不进行优化,问题也不大。
如果有兴趣,也可以进一步尝试优化。
至此,完整代码为:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printTheSame ( int cnt, char* st, char * ans ) {
for ( int i = 0; i < cnt; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );
}
}
void printZeroAndOne ( int cnt, char* ans ) {
int p = 0;
for ( int i = 0; i < cnt; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), "%d", p );
p = abs ( p - 1 );
}
}
int isTarget ( char* ans ) {
for ( int i = 1; i < strlen ( ans ); i++ ) {
if ( ans[i] == ans[i - 1] ) {
return 0;
}
}
return 1;
}
int main () {
int cas;
scanf ( "%d", &cas );
for ( int t = 0; t < cas; t++ ) {
printf ( "case #%d:\n", t );
char st[1000] = {0};
scanf ( "%s", st );
char ans[1000] = {0};
do {
if ( strlen ( ans ) ) {
strcpy ( st, ans );
for ( int i = 0; i < strlen ( ans ); i++ ) {
ans[i] = 0;
}
}
if ( strlen ( st ) == 1 ) {
printf ( "%d", st[0] - '0' + 1 );
} else {
int pos = 1;
char last, current;
while ( pos < strlen ( st ) ) {
last = st[pos - 1];
current = st[pos];
if ( last == current ) {
if ( last == '9' ) {
printTheSame ( pos - 2, st, ans );
if ( pos - 2 >= 0 ) {
sprintf ( ( ans + strlen ( ans ) ), "%c", st[pos - 2] + 1 );
} else {
sprintf ( ( ans + strlen ( ans ) ), "%c", '1' );
}
printZeroAndOne ( strlen ( st ) - pos + 1, ans );
break;
} else {
printTheSame ( pos - 1, st, ans );
int d;
sscanf ( ( st + pos - 1 ), "%02d", &d );
sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );
printZeroAndOne ( strlen ( st ) - pos - 1, ans );
break;
}
} else {
pos++;
}
if ( pos == strlen ( st ) ) {
printTheSame ( pos - 2, st, ans );
int d;
sscanf ( ( st + pos - 2 ), "%02d", &d );
sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );
}
}
}
} while ( !isTarget ( ans ) );
printf ( "%s", ans );
printf ( "\n" );
}
return 0;
}
2017-02-06_17-21一稿
2017-02-09_17-29二稿