问题:
给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。
——引自 百度2014校招笔试题目题解
问题的提法:
为代码简便,将问题等价地改为,求大于等于指定正整数的不重复数。由find()函数实现。
调用:
find( i + 1u )
原型:
unsigned find( unsigned );
算法:
以19922884u为例。
首先确定高位是否是重复数。即依次判断
1u
19u
199u
1992u
19922u
199228u
1992288u
是否是重复数。
如高位不是重复数,则当前数不变,并判断当前数是否是重复数。
例如对19u,由于1u不是重复数(一位正整数不是重复数,是显而易见的事。(if ( n < 10u ) return n;),所以判断19u是否是重复数(通过简单地判断19u的个位和十位是否相同。n % 10u == n /10u %10u)。
当当前数为199u时,高位(19u)不是重复数,当前数本身(119u)是重复数。
此时,将当前数加1,问题变为求大于等于200u的不重复数。
由于200u的高位不是重复数,而200u本身是重复数,所以经过了
n:2
n:20
之后,问题变成了求大于等于201u的不重复数。
201u不是重复数,所以回到求大于等于1992u的不重复数时,由于对于1992u来说,由于高位是重复数(返回值大于1992u/10u。 if ( n/10u <(t = find( n/10u)) )n = t * 10;),所以问题变成了求2010u的不重复数(n = t * 10;)。
2010u是不重复数,求大于等于19922u的不重复数变成了求大于等于20100u的不重复数。
但由于20100u的高位不是重复数,20100u本身是重复数(个位和十位相同),,所以问题又变成了求大于等于20101u的不重复数的问题( if ( n % 10u == n /10u %10u ) return find( n + 1u );)。
重复以上过程,可得结果为20101010。
代码:
1 #include <stdio.h> 2 3 unsigned find( unsigned );main( void ) 6 { 7 unsigned i ;( i = 19922884u ; i < 19922884u + 1u ; i++ )11 {, i , find( i + 1u ) );13 } ;16 }17 18 unsigned find( unsigned n )19 {20 unsigned t;, n ) ; ( n < 10u )25return n;( n / 10u < ( t = find( n / 10u ) ) )28n = t * 10u ;( n % 10u == n /10u % 10u )31return find( n + 1u ); n ;34 }变幻原是永恒,我们唯有用永恒的诺言制约世事的变幻。