给定 0 到 10^9 及其倒数之间的所有数字,有多少数字是混合的,奇数和偶数?
Given all numbers between 0 and 10^9 and its reverse, how many numbers are mixed, odd and even?
下一句是练习题。
我做了这个解决方案。它正在执行从 0 到 10^9 的循环。但它需要很多时间才能被执行。所以,我认为下一步是在数字和它的反面之间的结果中添加一个 hashmap 作为键,保存结果。
但是程序仍然在耗时。我想我可能缺少数学理论或另一种在更短时间内解决时间的方法。
计划:
#include <iostream>
#include <cmath>
using namespace std;
int reverseNumber(int n) {
int reverse = 0;
while (n > 0) {
reverse = reverse * 10;
reverse += n % 10;
n = n / 10;
}
return reverse;
}
string isNumberEvenOddOrMixed(int n) {
bool even = false;
bool odd = false;
while (n > 0) {
int rem = n % 10;
n = n / 10;
if (rem % 2 == 0)
even = true;
else
odd = true;
}
return even && odd ? "Mixed" : (even ? "Even" : "Odd");
}
int main(int argc, const char * argv[]) {
int even = 0, odd = 0, mixed = 0;
for (int i = 0; i < pow(10, 9); i++) {
// Verify if i already exists in the hashmap,
// if it is, just print the value saved.
int nReversed = reverseNumber(i);
int sum = i + nReversed;
string result = isNumberEvenOddOrMixed(sum);
if (result == "Even") even++;
else if (result == "Odd") odd++;
else mixed++;
// Save i and nReversed in a hashmap with the result
// hashmap[i] = result;
// hashmap[nReversed] = result;
cout << i << " + " << nReversed << " = " << sum << " : " << result << "\n";
}
cout << "Even: " << even << "\n";
cout << "Odd: " << odd << "\n";
cout << "Mixed: " << mixed << "\n";
return 0;
}
这些是从 0 到 10^2 的结果。我只是打印出来看看数字之间的关系:
0 + 0 = 0 : Odd
1 + 1 = 2 : Even
2 + 2 = 4 : Even
3 + 3 = 6 : Even
4 + 4 = 8 : Even
5 + 5 = 10 : Mixed
6 + 6 = 12 : Mixed
7 + 7 = 14 : Mixed
8 + 8 = 16 : Mixed
9 + 9 = 18 : Mixed
10 + 1 = 11 : Odd
11 + 11 = 22 : Even
12 + 21 = 33 : Odd
13 + 31 = 44 : Even
14 + 41 = 55 : Odd
15 + 51 = 66 : Even
16 + 61 = 77 : Odd
17 + 71 = 88 : Even
18 + 81 = 99 : Odd
19 + 91 = 110 : Mixed
20 + 2 = 22 : Even
21 + 12 = 33 : Odd
22 + 22 = 44 : Even
23 + 32 = 55 : Odd
24 + 42 = 66 : Even
25 + 52 = 77 : Odd
26 + 62 = 88 : Even
27 + 72 = 99 : Odd
28 + 82 = 110 : Mixed
29 + 92 = 121 : Mixed
30 + 3 = 33 : Odd
31 + 13 = 44 : Even
32 + 23 = 55 : Odd
33 + 33 = 66 : Even
34 + 43 = 77 : Odd
35 + 53 = 88 : Even
36 + 63 = 99 : Odd
37 + 73 = 110 : Mixed
38 + 83 = 121 : Mixed
39 + 93 = 132 : Mixed
40 + 4 = 44 : Even
41 + 14 = 55 : Odd
42 + 24 = 66 : Even
43 + 34 = 77 : Odd
44 + 44 = 88 : Even
45 + 54 = 99 : Odd
46 + 64 = 110 : Mixed
47 + 74 = 121 : Mixed
48 + 84 = 132 : Mixed
49 + 94 = 143 : Mixed
50 + 5 = 55 : Odd
51 + 15 = 66 : Even
52 + 25 = 77 : Odd
53 + 35 = 88 : Even
54 + 45 = 99 : Odd
55 + 55 = 110 : Mixed
56 + 65 = 121 : Mixed
57 + 75 = 132 : Mixed
58 + 85 = 143 : Mixed
59 + 95 = 154 : Mixed
60 + 6 = 66 : Even
61 + 16 = 77 : Odd
62 + 26 = 88 : Even
63 + 36 = 99 : Odd
64 + 46 = 110 : Mixed
65 + 56 = 121 : Mixed
66 + 66 = 132 : Mixed
67 + 76 = 143 : Mixed
68 + 86 = 154 : Mixed
69 + 96 = 165 : Mixed
70 + 7 = 77 : Odd
71 + 17 = 88 : Even
72 + 27 = 99 : Odd
73 + 37 = 110 : Mixed
74 + 47 = 121 : Mixed
75 + 57 = 132 : Mixed
76 + 67 = 143 : Mixed
77 + 77 = 154 : Mixed
78 + 87 = 165 : Mixed
79 + 97 = 176 : Mixed
80 + 8 = 88 : Even
81 + 18 = 99 : Odd
82 + 28 = 110 : Mixed
83 + 38 = 121 : Mixed
84 + 48 = 132 : Mixed
85 + 58 = 143 : Mixed
86 + 68 = 154 : Mixed
87 + 78 = 165 : Mixed
88 + 88 = 176 : Mixed
89 + 98 = 187 : Mixed
90 + 9 = 99 : Odd
91 + 19 = 110 : Mixed
92 + 29 = 121 : Mixed
93 + 39 = 132 : Mixed
94 + 49 = 143 : Mixed
95 + 59 = 154 : Mixed
96 + 69 = 165 : Mixed
97 + 79 = 176 : Mixed
98 + 89 = 187 : Mixed
99 + 99 = 198 : Mixed
Even: 24
Odd: 26
Mixed: 50
Program ended with exit code: 0
这里有几个小的优化思路:
1.
for (int i = 0; i < pow(10, 9); i++)
这个循环每次都在重新计算 10^9。只需执行一次并将其存储在 const 变量中
2.
我会将 "isNumberEvenOddOrMixed" 函数更改为 return 枚举值而不是字符串。它将使您的性能略有提高,而不必比较、创建和销毁字符串。
如果你只需要计算奇数、偶数和混合结果,你应该可以通过计算 1111111192 条记录(大约总数的 1/10)找到结果 [0, 10^9)
解决思路
0到9,全部计算即可。
对于剩余的值,请按以下方式思考。您不需要构建 table,而是使用概念。
设置一个table相同位数的值(令位数为r)
- 大小:9 列 10^(r-1) 行
- 值分布:左上角是该数字部分中最小的,向下时加1,向右时加10^(r-1)
10 20 30 40 50 60 70 80 90
11 21 31 41 51 61 71 81 91
12 22 32 42 52 62 72 82 92
...
...
19 29 39 49 59 69 79 89 99
看这个table,你会观察到任何值的结果都和右上角的结果相同(向上1,向右1) .
在这个意义上,你应该能够看到数字 r table,可以通过查找第一列和最后一列的值的结果来计算计数行,然后为每个计算的结果乘以正确的计数器(点 2 中其对角线上的值数,值在 1 到 9 之间)
- (10 的结果)* 1
- (11 的结果)* 2
- (12 的结果)* 3
- (13 的结果)* 4
- (14 的结果)* 5
- (15 的结果)* 6
- (16 的结果)* 7
- (17 的结果)* 8
- (18 的结果)* 9
- (19 的结果)* 9
- (29 的结果)* 8
- (39 的结果)* 7
- (49 的结果)* 6
- (59 的结果)* 5
- (69 的结果)* 4
- (79 的结果)* 3
- (89 的结果)* 2
- (99 的结果)* 1
计数器分布:左上角为1,向下移动时计数器加1,直到达到9。 1在右下角,向左移动计数器加1。
证明
假设您有一个值 'abcdefg' 并且('a' 不等于 1 且 'bcdefg' 不等于 0)。
在这种情况下,上面table中'abcdefg'的右上位置应该存在。
Rewrite 'abcdefg' as a*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... + f*10
+ g
Reverse of 'abcdefg' is g*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ... +
b*10 + a
Calculated value of 'abcdefg' is (a+g)*10^(r-1) + (b+f)*10^(r-2) +
(c+e)*10^(r-3) + ... + (f+b)*10 + (g+a)
'abcdefg'右上角的值是'abcdefg' + 10^(r-1) - 1,我们可以写成'a"bcdefg"' where a" = a+ 1 和 g" = g-1
Rewrite 'a"bcdefg"' as a"*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... +
f*10 + g"
Reverse of 'a"bcdefg"' is g"*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ...
+ b*10 + a"
Calculated value of 'a"bcdefg"' is (a"+g")*10^(r-1) + (b+f)*10^(r-2) +
(c+e)*10^(r-3) + ... + (f+b)*10 + (g"+a")
Since g"+a" = g-1 + a+1 = g+a, we have calculated value of 'a"bcdefg"'
is (a+g)*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10
+ (g+a) and is equal to calculated value of 'abcdefg'
这证明计算值将与其右上角元素的计算值相同
下一句是练习题。
我做了这个解决方案。它正在执行从 0 到 10^9 的循环。但它需要很多时间才能被执行。所以,我认为下一步是在数字和它的反面之间的结果中添加一个 hashmap 作为键,保存结果。
但是程序仍然在耗时。我想我可能缺少数学理论或另一种在更短时间内解决时间的方法。
计划:
#include <iostream>
#include <cmath>
using namespace std;
int reverseNumber(int n) {
int reverse = 0;
while (n > 0) {
reverse = reverse * 10;
reverse += n % 10;
n = n / 10;
}
return reverse;
}
string isNumberEvenOddOrMixed(int n) {
bool even = false;
bool odd = false;
while (n > 0) {
int rem = n % 10;
n = n / 10;
if (rem % 2 == 0)
even = true;
else
odd = true;
}
return even && odd ? "Mixed" : (even ? "Even" : "Odd");
}
int main(int argc, const char * argv[]) {
int even = 0, odd = 0, mixed = 0;
for (int i = 0; i < pow(10, 9); i++) {
// Verify if i already exists in the hashmap,
// if it is, just print the value saved.
int nReversed = reverseNumber(i);
int sum = i + nReversed;
string result = isNumberEvenOddOrMixed(sum);
if (result == "Even") even++;
else if (result == "Odd") odd++;
else mixed++;
// Save i and nReversed in a hashmap with the result
// hashmap[i] = result;
// hashmap[nReversed] = result;
cout << i << " + " << nReversed << " = " << sum << " : " << result << "\n";
}
cout << "Even: " << even << "\n";
cout << "Odd: " << odd << "\n";
cout << "Mixed: " << mixed << "\n";
return 0;
}
这些是从 0 到 10^2 的结果。我只是打印出来看看数字之间的关系:
0 + 0 = 0 : Odd
1 + 1 = 2 : Even
2 + 2 = 4 : Even
3 + 3 = 6 : Even
4 + 4 = 8 : Even
5 + 5 = 10 : Mixed
6 + 6 = 12 : Mixed
7 + 7 = 14 : Mixed
8 + 8 = 16 : Mixed
9 + 9 = 18 : Mixed
10 + 1 = 11 : Odd
11 + 11 = 22 : Even
12 + 21 = 33 : Odd
13 + 31 = 44 : Even
14 + 41 = 55 : Odd
15 + 51 = 66 : Even
16 + 61 = 77 : Odd
17 + 71 = 88 : Even
18 + 81 = 99 : Odd
19 + 91 = 110 : Mixed
20 + 2 = 22 : Even
21 + 12 = 33 : Odd
22 + 22 = 44 : Even
23 + 32 = 55 : Odd
24 + 42 = 66 : Even
25 + 52 = 77 : Odd
26 + 62 = 88 : Even
27 + 72 = 99 : Odd
28 + 82 = 110 : Mixed
29 + 92 = 121 : Mixed
30 + 3 = 33 : Odd
31 + 13 = 44 : Even
32 + 23 = 55 : Odd
33 + 33 = 66 : Even
34 + 43 = 77 : Odd
35 + 53 = 88 : Even
36 + 63 = 99 : Odd
37 + 73 = 110 : Mixed
38 + 83 = 121 : Mixed
39 + 93 = 132 : Mixed
40 + 4 = 44 : Even
41 + 14 = 55 : Odd
42 + 24 = 66 : Even
43 + 34 = 77 : Odd
44 + 44 = 88 : Even
45 + 54 = 99 : Odd
46 + 64 = 110 : Mixed
47 + 74 = 121 : Mixed
48 + 84 = 132 : Mixed
49 + 94 = 143 : Mixed
50 + 5 = 55 : Odd
51 + 15 = 66 : Even
52 + 25 = 77 : Odd
53 + 35 = 88 : Even
54 + 45 = 99 : Odd
55 + 55 = 110 : Mixed
56 + 65 = 121 : Mixed
57 + 75 = 132 : Mixed
58 + 85 = 143 : Mixed
59 + 95 = 154 : Mixed
60 + 6 = 66 : Even
61 + 16 = 77 : Odd
62 + 26 = 88 : Even
63 + 36 = 99 : Odd
64 + 46 = 110 : Mixed
65 + 56 = 121 : Mixed
66 + 66 = 132 : Mixed
67 + 76 = 143 : Mixed
68 + 86 = 154 : Mixed
69 + 96 = 165 : Mixed
70 + 7 = 77 : Odd
71 + 17 = 88 : Even
72 + 27 = 99 : Odd
73 + 37 = 110 : Mixed
74 + 47 = 121 : Mixed
75 + 57 = 132 : Mixed
76 + 67 = 143 : Mixed
77 + 77 = 154 : Mixed
78 + 87 = 165 : Mixed
79 + 97 = 176 : Mixed
80 + 8 = 88 : Even
81 + 18 = 99 : Odd
82 + 28 = 110 : Mixed
83 + 38 = 121 : Mixed
84 + 48 = 132 : Mixed
85 + 58 = 143 : Mixed
86 + 68 = 154 : Mixed
87 + 78 = 165 : Mixed
88 + 88 = 176 : Mixed
89 + 98 = 187 : Mixed
90 + 9 = 99 : Odd
91 + 19 = 110 : Mixed
92 + 29 = 121 : Mixed
93 + 39 = 132 : Mixed
94 + 49 = 143 : Mixed
95 + 59 = 154 : Mixed
96 + 69 = 165 : Mixed
97 + 79 = 176 : Mixed
98 + 89 = 187 : Mixed
99 + 99 = 198 : Mixed
Even: 24
Odd: 26
Mixed: 50
Program ended with exit code: 0
这里有几个小的优化思路:
1.
for (int i = 0; i < pow(10, 9); i++)
这个循环每次都在重新计算 10^9。只需执行一次并将其存储在 const 变量中
2.
我会将 "isNumberEvenOddOrMixed" 函数更改为 return 枚举值而不是字符串。它将使您的性能略有提高,而不必比较、创建和销毁字符串。
如果你只需要计算奇数、偶数和混合结果,你应该可以通过计算 1111111192 条记录(大约总数的 1/10)找到结果 [0, 10^9)
解决思路
0到9,全部计算即可。
对于剩余的值,请按以下方式思考。您不需要构建 table,而是使用概念。
设置一个table相同位数的值(令位数为r)
- 大小:9 列 10^(r-1) 行
- 值分布:左上角是该数字部分中最小的,向下时加1,向右时加10^(r-1)
10 20 30 40 50 60 70 80 90
11 21 31 41 51 61 71 81 91
12 22 32 42 52 62 72 82 92
...
...
19 29 39 49 59 69 79 89 99
看这个table,你会观察到任何值的结果都和右上角的结果相同(向上1,向右1) .
在这个意义上,你应该能够看到数字 r table,可以通过查找第一列和最后一列的值的结果来计算计数行,然后为每个计算的结果乘以正确的计数器(点 2 中其对角线上的值数,值在 1 到 9 之间)
- (10 的结果)* 1
- (11 的结果)* 2
- (12 的结果)* 3
- (13 的结果)* 4
- (14 的结果)* 5
- (15 的结果)* 6
- (16 的结果)* 7
- (17 的结果)* 8
- (18 的结果)* 9
- (19 的结果)* 9
- (29 的结果)* 8
- (39 的结果)* 7
- (49 的结果)* 6
- (59 的结果)* 5
- (69 的结果)* 4
- (79 的结果)* 3
- (89 的结果)* 2
- (99 的结果)* 1
计数器分布:左上角为1,向下移动时计数器加1,直到达到9。 1在右下角,向左移动计数器加1。
证明
假设您有一个值 'abcdefg' 并且('a' 不等于 1 且 'bcdefg' 不等于 0)。 在这种情况下,上面table中'abcdefg'的右上位置应该存在。
Rewrite 'abcdefg' as a*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... + f*10 + g
Reverse of 'abcdefg' is g*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ... + b*10 + a
Calculated value of 'abcdefg' is (a+g)*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g+a)
'abcdefg'右上角的值是'abcdefg' + 10^(r-1) - 1,我们可以写成'a"bcdefg"' where a" = a+ 1 和 g" = g-1
Rewrite 'a"bcdefg"' as a"*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... + f*10 + g"
Reverse of 'a"bcdefg"' is g"*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ... + b*10 + a"
Calculated value of 'a"bcdefg"' is (a"+g")*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g"+a")
Since g"+a" = g-1 + a+1 = g+a, we have calculated value of 'a"bcdefg"' is (a+g)*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g+a) and is equal to calculated value of 'abcdefg'
这证明计算值将与其右上角元素的计算值相同