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

ddvv

我看出来了，这个网易笔试题

ydhbzkx

我觉的可以这样求,找到a中非0的最低位,此位减1,把此位的上一位加1,如果上一位是9就上推一位,把比加1位小的位全取0,然后从个位开始把原来取掉的位的和分掉.

[ 本帖最后由 ydhbzkx 于 2007-10-29 23:17 编辑 ]

cheng_lai_shun

LZ,可能有溢出吗？

gqgl

luguo

tyc611

原帖由 oceanpea 于 2007-10-31 17:15 发表



这个a怎么分解的阿？分解成x[k]...x[1]a9...9b0...0 ？
能写详细一点么，没看明白。。。

1. 
   
2. #include <iostream>
   
3. #include <string>
   
4. #include <sstream>
   
5. using namespace std;
   
6. 
   
7. /**
   
8. * 计算正数num1的上临近数num2，num2满足:
   
9. *    (1) num2 > num1;  
   
10. *    (2) num1、num2各位数字之和相等（十进制表示）;  
    
11. *    (3) num2是满足(1)、(2)条件的最小正数
    
12. * @param num: num1的值，应为正数
    
13. * @return: 如果@param num为正数，则返回num1的上临近数num2;否则返回-1
    
14. */
    
15. int get_up_nearest(size_t num)
    
16. {
    
17.     if (num == 0)
    
18.         return -1;    // 0没有上临近数
    
19. 
    
20.     ostringstream oss;
    
21.     oss << num;
    
22.     string src("0");  // 保证下面的a的存在，并且不会影响结果
    
23.     src += oss.str();
    
24. 
    
25.    
    
26.     // 把num表示为x[k]...x[1]a9...9b0...0，其中a != 9, b != 0（前面的x[i]可能没有）
    
27.     // step1：将原串变为x[k]...[1]ab0...09...9
    
28.     // step2：再次变换为x[k]...x[1](a+1)0...0(b-1)9...9，over
    
29.     typedef string::size_type pos_t;
    
30. 
    
31.     pos_t b = src.find_last_not_of('0');
    
32.     pos_t a = src.find_last_not_of('9', b - 1);
    
33. 
    
34.     // 计算x[k]...[1]ab0...09...9中"最后一个"0的位置，即x[k]...[1]ab0...c9...9
    
35.     pos_t c = src.length() - b + a;
    
36.     ++src[a];
    
37.     src[c] = src[b] - 1;
    
38.     for (pos_t i = a + 1; i < c; ++i)
    
39.         src[i] = '0';
    
40.     for (pos_t i = c + 1; i < src.length(); ++i)
    
41.         src[i] = '9';
    
42.    
    
43.     int res = atoi(src.c_str());
    
44. 
    
45.     return res;   
    
46. }
    
47. 
    
48. /**
    
49. * 计算正数num1的下临近数num2，num2满足：
    
50. *    (1) num2 < num1;  
    
51. *    (2) num1、num2各位数字之和相等（十进制表示）;  
    
52. *    (3) num2是满足(1)、(2)条件的最大正数
    
53. * @param num: num1的值；对于某些特殊的num值，可能不存在相应的下临近数
    
54. * @return: 如果存在下临近数，则返回下临近数；否则返回-1
    
55. * @note: 并不是所有数都存在下临近数，例如0~9，还如x99...9这类数就不存在下临近数
    
56. */
    
57. int get_down_nearest(size_t num)
    
58. {
    
59.     if (num < 10)
    
60.         return -1;   // 不存在下临近数
    
61.    
    
62.     ostringstream oss;
    
63.     oss << num;
    
64.     string src = oss.str();
    
65.    
    
66.    
    
67.     // 把num表示为x[k]...x[1]a0...0b9...9，其中a != 0, b != 9
    
68.     // step1：x[k]...x[1]a9...90...0b
    
69.     // step2：x[k]...x[1](a-1)9...9(b+1)0...0
    
70.     typedef string::size_type pos_t;
    
71. 
    
72.     pos_t b = src.find_last_not_of('9');
    
73.     if (b == string::npos || b == 0)
    
74.         return -1;   // num形如：x99...9，此时不存在下临近数
    
75.    
    
76.     pos_t a = src.find_last_not_of('0', b - 1);
    
77.    
    
78.     // 计算x[k]...x[1]a9...90...0b中"第一个"0的位置，即x[k]...x[1]a9...9c...0b
    
79.     pos_t c = src.length() - b + a;   
    
80.     --src[a];
    
81.     src[c] = src[b] + 1;
    
82.     for (pos_t i = a + 1; i < c; ++i)
    
83.         src[i] = '9';
    
84.     for (pos_t i = c + 1; i < src.length(); ++i)
    
85.         src[i] = '0';
    
86.    
    
87.     int res = atoi(src.c_str());
    
88.    
    
89.     return res;   
    
90. }
    
91. 
    
92. void test(int num)
    
93. {
    
94.     cout << "num = " << num << ", up-nearest = " << get_up_nearest(num)
    
95.         << ", down-nearest = " << get_down_nearest(num) << endl;
    
96. }
    
97. 
    
98. int main()
    
99. {
    
100.     test(113);
     
101.     test(10);
     
102.     test(200);
     
103.     test(1);
     
104.     test(2);
     
105.     test(9);
     
106.     test(99);
     
107.     test(1999);
     
108.     test(4684);
     
109.     test(4660500);
     
110.    
     
111.     return 0;
     
112. }
     

复制代码

输出：
num = 113, up-nearest = 122, down-nearest = 104
num = 10, up-nearest = 100, down-nearest = 1
num = 200, up-nearest = 1001, down-nearest = 110
num = 1, up-nearest = 10, down-nearest = -1
num = 2, up-nearest = 11, down-nearest = -1
num = 9, up-nearest = 18, down-nearest = -1
num = 99, up-nearest = 189, down-nearest = -1
num = 1999, up-nearest = 2899, down-nearest = -1
num = 4684, up-nearest = 4693, down-nearest = 4675
num = 4660500, up-nearest = 4661004, down-nearest = 4660410

blue_galaxy

各位大牛数学没学太好啊~~~
不知道有数根这个东西吗

大部分的数加9即可

也有特殊情况 特殊处理 不多说了