算法求一个数a的下一个临近数b，详情如下

erduo100

原帖由 sanbiangongzi 于 2007-10-26 22:28 发表
假设题目描述的b对正整数a的关系可以表示为函数b=foo(a);
。。。。

你从引理2如何得出foo(8620)  = 8701;

sanbiangongzi

高手，虽然和我的想法一样，但是描述的比我清楚多了。
赞

sanbiangongzi

原帖由 erduo100 于 2007-10-27 08:07 发表

你从引理2如何得出foo(8620)  = 8701;

引理2：foo(X[N]*10^N + ... + X[j+1]*10^(j+1) + X[j]*10^j)
= X[N]*10^N + ... + X[j+1]*10^(j+1) + 1*10^(j+1) +(X[j]-1)
其中X[N]!=0,X[j+1]!=9,X[j]!=0,j=0,1,2,... (待证明)
例如：
foo(951)   = 960;
foo(8620)  = 8701;
foo(57300) = 58002;

对应8620,j就是1
X[j]就是2
x[j+1]就是6

foo(8620)
=foo(8*10^3 + 6*10^2 + 2*10^1)
=8*10^3 +  6*10^2 + 1*10^2 + (2-1)
=8701

Qshine

我碰到类似的一个题，但不同的是这个a不一定是整数，它可能是一个相当长的由0-9的数学组成的字符串。要求下一个串b，使得a,b各位数字之和相等，并且从数的观点来看，值最接近a。

kaios

从低位起将第一位不为0的数减1，将这个1加到他的高一位，再将该位上剩余的数加到最低位。
若只有最高位不为0，如果最高位为1，则补0。若只有最高位不为0，且最高位不为1，则将最高位减1补到末尾。
比如：
a=113,则b=112＋10
a=10,则b=100
a=200,则b=1001
每个整数都用数组保存！负数应该可以相似的处理！

tyc611

原帖由 kaios 于 2007-10-27 10:54 发表
从低位起将第一位不为0的数减1，将这个1加到他的高一位，再将该位上剩余的数加到最低位。
若只有最高位不为0，如果最高位为1，则补0。若只有最高位不为0，且最高位不为1，则将最高位减1补到末尾。
比如：
a= ...

没看得明白，请问这个数（1999）怎么处理？

kaios

没考虑进位！2899不知道对不！如果有连续的9应该从最高的9减吧！
我想的这个没有数学证明，欢迎大家批评指正！

kaios

10 楼正解！

erduo100

原帖由 tyc611 于 2007-10-26 23:59 发表
把a表示为x[k]...x[1]a9...9b0...0，其中a != 9, b != 0（前面的x可能没有）
step1：将原串变为x[k]...[1]ab0...09...9
step2：再次变换为x[k]...x[1](a+1)0...0(b-1)9...9，over

另外，对于一个相关问题， ...

为什么要分两步?

tyc611

原帖由 erduo100 于 2007-10-27 21:32 发表


为什么要分两步?

只是为了方便叙述，这样可能看得明白点