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

fertiland

求一个数a的下一个临近数b，满足如下条件:
1 b>a
2 a的各个位的数字之和等于b的各个位之和
3 b是满足1,2条件的最小数
比如
a=113则b=122
a=10  则b=100
a=200则b=1001
求通用的计算方法int fun(int a)
返回值为b
[不用蛮力法]

[ 本帖最后由 fertiland 于 2007-10-26 18:59 编辑 ]

scutan

原帖由 fertiland 于 2007-10-26 18:36 发表
求一个数a的下一个临近数b，满足如下条件:
1 b>a
2 a的各个位的数字之和等于b的各个位之和
3 b是满足1,2条件的最小数
比如
a=113则b=122
a=10  则b=100
a=200则b=1001
求通用的计算方法int fun(int a)
...

写了一个, 也许还有效率更高的!

1. 
   
2. #include<stdio.h>
   
3. int count(int a)
   
4. {
   
5.         int i = 0;
   
6.         do
   
7.         {
   
8.                 i += a % 10;
   
9.         }while (a = a / 10);
   
10.         return i;
    
11. }
    
12. 
    
13. int fun(int a)
    
14. {
    
15.         int i = count(a);
    
16.         while (1)
    
17.         {
    
18.                 a++;
    
19.                 if (count(a) == i)
    
20.                         return a;
    
21.         }
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.         int a;
    
27.         int i;
    
28.         scanf("%d", &a);
    
29.         i = fun(a);
    
30.         printf("out : %d\n", i);
    
31.         return 0;
    
32. }
    

复制代码

fertiland

怎么都想到的是蛮力法解？
谢谢，动作很快啊

[ 本帖最后由 fertiland 于 2007-10-26 18:59 编辑 ]

sanbiangongzi

原帖由 jamesr 于 2007-10-26 19:46 发表
非蛮力：

#include
static char array[10]={0};

void put(int a)
{
        int s=0;
        for(int i=0;i

可惜是错误的算法
你试一下
fun(199100)
fun(19100)

你的算法结果是错的

sanbiangongzi

假设题目描述的b对正整数a的关系可以表示为函数b=foo(a);
引理1：foo(X[j]*10^j)
= 1*10^(j+1) + (X[j]-1)
其中X[j]!=0,j=0,1,2,... (待证明)
例如：
foo(1)   = 10;
foo(20)  = 101;
foo(300) = 1002;
引理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;
引理3：foo(X[N]*10^N + ... + X[i+1]*10^(i+1) + X*10^i + ... + X[j+1]*10^(j+1) + X[j]*10^j)
= X[N]*10^N + ... + X[i+1]*10^(i+1) +1*10^(i+1) + (X[j]-1)*10^(i-j) + X*10^(i-j-1) + ... + X[j+1]*10^0
其中X[N]!=0,X[j]!=0,X[j+1]直到X == 9, i,j=0,1,2,... (待证明)
例如：
foo(1591)     = 1609;
foo(169920)   = 170199;
foo(17999300) = 18002999;
一个正整数a肯定可以表示成
a = X[N]*10^N + ... + X[i+1]*10^(i+1) + X*10^i + ... + X[j+1]*10^(j+1) + X[j]*10^j
的形式
根据引理3就可以解
如果程序来实现，只要分解出a的每一十进制位的值即可。
关于引理证明问题，我觉得引理看起来很自然，一时想不到简单明了方法证明之。
请诸位高手指点

如果a是负数，研究中……


-----
#include <stdio.h>
unsigned int power(unsigned int base, unsigned int n)
{
unsigned int val;

val = 1;
while(n--)
{
  val *= base;
}
return val;
}
unsigned int fill_digit(unsigned int digit,
  unsigned int *digitArray)
{
int i;
i = 0;
do
{
  digitArray = digit%10;
  digit /= 10;
  i++;
}while(digit);
return i;
}
unsigned int foo(unsigned int a)
{
unsigned int digitArray[20];
unsigned int digitWidth;
unsigned int b;
unsigned int i;
unsigned int j;
unsigned int idx;
digitWidth = fill_digit(a, digitArray);
for(idx=0; idx<digitWidth; idx++)
{
  if(0 != digitArray[idx])
  {
   j = idx;
   i = idx;
   break;
  }
}

idx++;
if(idx<digitWidth)
{
  if(9 == digitArray[idx])
  {
   for(; idx<digitWidth; idx++)
   {
    if(9 == digitArray[idx])
    {
     i = idx;
    }
    else
    {
     break;
    }
   }
  }
}
b = 0;
for(idx=digitWidth-1; idx>=0; idx--)
{
  if(idx>i)
  {
   b += digitArray[idx]*power(10, idx);
   continue;
  }
  if(idx>j)
  {
   b += 9*power(10, idx-j-1);
   continue;
  }
  break;
}
b += power(10, i+1) + (digitArray[j]-1)*power(10, i-j);
return b;
}
int main(int argc, char *argv[])
{
unsigned int a;
if(argc > 1)
{
  a = atoi(argv[1]);
  if(a)
  {
   printf("%d -- %d\n", a, foo(a));
  }
}
return 0;
}

-----

[ 本帖最后由 sanbiangongzi 于 2007-10-27 08:23 编辑 ]

tyc611

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

另外，对于一个相关问题，找与a的临近数b，b满足：b < a，且b为满足b < a的最大数，a和b各位数之和相同
相似的解决方案：把a表示为x[k]...x[1]a0...0b9...9，其中a != 0, b != 9
step1：x[k]...x[1]a9...90...0b
step2：x[k]...x[1](a-1)9...9(b+1)0...0

源程序就不写了

[[i] 本帖最后由 tyc611 于 2007-10-27 00:04 编辑 [/i]]