算法:求比指定数大且最小的“不重复数”问题的高效实现

问题:

  给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如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 }变幻原是永恒,我们唯有用永恒的诺言制约世事的变幻。

算法:求比指定数大且最小的“不重复数”问题的高效实现

相关文章:

你感兴趣的文章:

标签云: