代码之家 › 专栏 › 技术社区 › Oscar

给定0到10^9之间的所有数字及其相反的数字,有多少数字是混合的,奇数和偶数?

analysis math algorithm c++ java

-5

Oscar · 技术社区 · 8 年前

下一个陈述是一个练习的问题。

但该计划仍在耗费时间。我想我可能错过了一个数学理论或另一种在更短时间内解决时间问题的方法。

程序:

#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

2 回复 | 直到 8 年前

hk6279 8 年前

如果您只需要计算奇数、偶数和混合结果,您应该能够通过计算[0,10^9)的1111111192条记录(约占总数的1/10)来找到结果

解决方案想法

对于0到9,只需全部计算即可。

对于其余值,请如下所示。您不需要构建表,而是使用这个概念。

- 大小:9列,10^(r-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

查看此表,您会发现任何值的结果都将与其右上角的结果相同(向上1,向右1)。
从这个意义上说,您应该能够看到数字r表, 可以通过查找第一列和最后一行的值的结果来计算计数,然后为每个结果计算一个正确的计数器 (第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)。在这种情况下,上表中“abcdefg”的右上角位置应该存在。

将“abcdefg”重写为a*10^(r-1)+b*10^(r-2)+c*10^-(r-3)+…+f*10 +克

“abcdefg”的反面是g*10^(r-1)+f*10^(r-2)+e*10^-(r-3)++ b*10+a

“abcdefg”的计算值为(a+g)*10^(r-1)+(b+f)*10*(r-2)+ (c+e)*10^(r-3)+…+(f+b)*10+(g+a)

“abcdefg”右上角的值为“abcddefg”+10^(r-1)-1。我们可以将其写为“a”bcdefg“”,其中a“=a+1,g”=g-1

将“a”bcdefg“”重写为a“*10^(r-1)+b*10^(r-2)+c*10^-(r-3)++ f*10+g“

“a”bcdefg“”的反面是g“*10^(r-1)+f*10^(r-2)+e*10^-(r-3)+。。。

“a”bcdefg“”的计算值为(a”+g“)*10^(r-1)+(b+f)*10*(r-2)+ (c+e)*10^(r-3)+…+(f+b)*10+(g“+a”)

“a”bcdefg“”的计算值是(a+g)*10^(r-1)+(b+f)*10*(r-2)+(c+e)*10#(r-3)+…+(f+b)*10 +(克+年) 和 等于“abcdefg”的计算值

这证明计算值将与其右上角元素的计算值相同

bennji_of_the_overflow 8 年前

以下是一些小的优化想法:

for (int i = 0; i < pow(10, 9); i++)

此循环每次都在重新计算10^9。只需执行一次,并将其存储在常量变量中