Главная » C++ » java - Учитывая все числа от 0 до 10 ^ 9 и наоборот, сколько чисел смешано, нечетно и четно?

java — Учитывая все числа от 0 до 10 ^ 9 и наоборот, сколько чисел смешано, нечетно и четно?

Следующее утверждение является проблемой для упражнения.

введите описание изображения здесь

Я сделал это решение. Это выполняет цикл от 0 до 10 ^ 9. Но это занимает много времени, чтобы быть казненным. Итак, следующий шаг, который я подумал, это добавить хеш-карту в результат между числом и его реверсом в качестве ключей, сохранив результат.

Но программа по-прежнему занимает много времени. Я предполагаю, что мне не хватает математической теории или другого подхода к решению времени за меньшее время.

Программа:

#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

-5

Решение

Если вам просто нужно сосчитать нечетный, четный и смешанный результат, вы сможете найти результат, рассчитав 1111111192 записей (примерно 1/10 от общего числа) для [0, 10 ^ 9)

Идея решения

Для 0 до 9, просто посчитайте все это.

Для оставшихся значений подумайте, как показано ниже. Вам не нужно строить таблицу, но используйте концепцию.

  1. Настройте таблицу для значения того же количества цифр (пусть номер цифры будет r)

    • размер: 9 столбцов с 10 ^ (р-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 и справа на 1).

  2. В этом смысле вы должны увидеть таблицу цифр 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’ как * 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) + … +
б * 10 + а

Расчетное значение abcdefg: (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», где a «= a + 1 и g» = g-1.

Перепишите «a bcdefg» как «* 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) + …
+ b * 10 + a «

Расчетное значение ‘a «bcdefg»‘ равно (a «+ g») * 10 ^ (r-1) + (b + f) * 10 ^ (r-2) +
(c + e) ​​* 10 ^ (r-3) + … + (f + b) * 10 + (g «+ a»)

Поскольку g «+ a» = g-1 + a + 1 = g + a, мы имеем вычисленное значение ‘a «bcdefg»‘
это (a + g) * 10 ^ (r-1) + (b + f) * 10 ^ (r-2) + (c + e) ​​* 10 ^ (r-3) + … + (f + б) * 10
+ (г + а) а также равно вычисленному значению ‘abcdefg’

Это доказывает, что вычисленное значение будет таким же, как вычисленное значение его верхнего правого элемента

1

Другие решения

Вот пара небольших идей по оптимизации:

1.

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

Этот цикл пересчитывает 10 ^ 9 каждый раз. Просто сделайте это один раз и сохраните в переменной const

2.

Я бы изменил функцию isNumberEvenOddOrMixed, чтобы она возвращала значение перечисления вместо строки. Это даст вам небольшое увеличение производительности без необходимости сравнивать, создавать и уничтожать строки.

1

Источник
По вопросам рекламы ammmcru@yandex.ru
Web-Answers © 2024 Наверх
Adblock
detector