| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
V-Isa
Гость
|
 Добавлено: Ср Фев 18 2004 16:52 Заголовок сообщения: Алгоритм расчета количества "счастливых" чисел |
 |
|
Необходим алгоритм определения количества "счастливых" чисел в заданном диапазоне. Обычный перебор не подходит, так как разрадность числа может быть очень большой. Счастливым называется число, сумма цифр которого слева равна сумме цифр справа.
Например, 123006 - счастливое, 12306 - нет. |
|
| Вернуться к началу |
|
 |
unknown
Гость
|
| Добавлено: Чт Фев 19 2004 14:47 Заголовок сообщения: |
|
|
Может попробовать через строку...
Число переводишь в строку, находишь ее длину, разбиваешь на две (первая половинка слева, вторая справа), потом последовательно каждый символ 1-ой строки переводишь в число и складываешь -> получаешь сумму первых цыфр, тоже самое со второй...
переборов вроде немного |
|
| Вернуться к началу |
|
|
GREA
Зарегистрирован: 14.05.2003
Сообщения: 758
Откуда: Новосибирск
|
| Добавлено: Чт Фев 19 2004 19:26 Заголовок сообщения: |
|
|
| Это комбинаторная задача. Сначала считаешь сколько у тебя подходящих пар упорядоченных наборов чисел (чтобы суммы совпадали), а потом все возможные перестановки без повторений для каждой пары (ну и, разумеется, отметаешь внедиапазонные варианты). |
|
| Вернуться к началу |
|
|
wildwind
Зарегистрирован: 03.02.2004
Сообщения: 268
Откуда: Москва
|
| Добавлено: Чт Фев 19 2004 20:03 Заголовок сообщения: |
|
|
| GREA писал(а): | | Это комбинаторная задача. |
Верно.
Давайте двигаться к цели постепенно.
Немного упростим задачу. Пусть требуется найти количество счастливых среди всех 2*k-значных чисел. То есть в диапазоне (100...000 - 999...999).
Разделим такие числа на половинки - левую и правую, по k знаков. Очевидно, что сумма цифр в левой половинке может быть от 1 до 9*k, а в правой от 0 до 9*k (но 0 нас не интересует, так как слева его быть не может). Итак, для каждого s от 1 до 9*k найдем кол-во чисел слева и справа, с суммой цифр s (они не равны, потому что справа могут быть ведущие нули, а слева нет), перемножим и получим кол-во счастливых чисел с суммой s. И так для всех.
Итак, задача сводится к нахождению количества k-значных чисел с суммой s. Нюхом чую, что тут можно найти рекуррентную формулу...
Пока так. Кто продолжит? |
|
| Вернуться к началу |
|
|
GREA
Зарегистрирован: 14.05.2003
Сообщения: 758
Откуда: Новосибирск
|
| Добавлено: Пт Фев 20 2004 16:42 Заголовок сообщения: |
|
|
Пожалуй, я продолжу.
На мой взгляд, задачу можно существенно оптимизировать.
Информация к размышелнию:
Во-первых, если ориентироваться на переборный вариант, то нам достаточно подсчитать только те случаи, когда сумма цифр не превышает 13 (это вполне естественное требование исходя из симметричности ситутации, если не учитывать начальный ноль) Вот частотная статистика:
0, 27 : 1
1, 26 : 3
2, 25 : 6
3, 24 : 10
4, 23 : 15
5, 22 : 21
6, 21 : 28
7, 20 : 36
8, 19 : 45
9, 18 : 55
10,17 : 63
11,16 : 69
12,15 : 73
13,14 : 75
Интересно также, что принцип двойственноси наблюдается и
Для 100-999
0 : 0
1, 27 : 1
2, 26 : 3
3, 25 : 6
4, 24 : 10
5, 23 : 15
6, 22 : 21
7, 21 : 28
8, 20 : 36
9, 19 : 45
10,18: 54
11,17: 61
12,16: 66
13,15: 69
14: 70
Анализируя наборы по три цифры, можно видеть, что если число случаев, содержащих 0 в левой части поделить на 3 (это избавит от первого 0. Нужно так же помнить о случаях, когда у нас есть два (три и более для больших чисел) нуля) мы сможем делать все в общем случае для наборов ровно по три цифры каждый.
Если решать комбинаторно, то первоначальное упорядочивание наборов (к минимальному числу) существенно упростит задачу.
Какие мысли? |
|
| Вернуться к началу |
|
|
wildwind
Зарегистрирован: 03.02.2004
Сообщения: 268
Откуда: Москва
|
| Добавлено: Пт Фев 20 2004 20:52 Заголовок сообщения: |
|
|
Вот мой анализ:
| Код: | Разрядность k 8-значные числа
Сумма
цифр 1 2 3 4 5 6 Слева Справа Совп.
------+---------------------------+-------------------
1 1 1 1 1 1 1 1 4 4
2 1 2 3 4 5 6 4 10 40
3 1 3 6 10 15 21 10 20 200
4 1 4 10 20 35 56 20 35 700
5 1 5 15 35 70 126 35 56 1960
6 1 6 21 56 126 252 56 84 4704
7 1 7 28 84 210 462 84 120 10080
8 1 8 36 120 330 792 120 165 19800
9 1 9 45 165 495 1287 165 220 36300
10 9 54 219 714 2001 219 282 61758
11 8 61 279 992 2992 279 348 97092
12 7 66 342 1330 4317 342 415 141930
13 6 69 405 1725 6027 405 480 194400
14 5 70 465 2170 8162 465 540 251100
15 4 69 519 2654 10746 519 592 307248
16 3 66 564 3162 13782 564 633 357012
17 2 61 597 3675 17247 597 660 394020
18 1 54 615 4170 21087 615 670 412050
19 45 615 4620 25212 615 660 405900
20 36 597 4998 29496 597 633 377901
21 28 564 5283 33787 564 592 333888
22 21 519 5460 37917 519 540 280260
23 15 465 5520 41712 465 480 223200
24 10 405 5460 45002 405 415 168075
25 6 342 5283 47631 342 348 119016
26 3 279 4998 49467 279 282 78678
27 1 219 4620 50412 219 220 48180
28 165 4170 50412 165 165 27225
29 120 3675 49467 120 120 14400
30 84 3162 47631 84 84 7056
31 56 2654 45002 56 56 3136
32 35 2170 41712 35 35 1225
33 20 1725 37917 20 20 400
34 10 1330 33787 10 10 100
35 4 992 29496 4 4 16
36 1 714 25212 1 1 1
37 495 21087
38 330 17247 Всего 4379055
39 210 13782 сч. чисел
.. ... .....
|
В таблице количество k-значных чисел с данной суммой. В правой части таблицы расчет для 8-значных чисел (по 4 слева и справа)
Рекуррентная формула все-таки есть. Количество k-значных чисел с суммой S в левой части (без ведущих нулей) обозначим как L(k,s), в правой части соответственно R(k,s). Тогда
| Код: |
s k
--- ---
\ \
L(k,s) = / L(k-1,s) , R(k,s) = / L(i,s)
--- ---
i=max(s-9,0) i=1
|
Жаль, здесь нельзя прицепить исходный xls, там все формулы видны... 
Вариант с перебором имхо все же тупиковый,
| Цитата: | | так как разрадность числа может быть очень большой. |
Не будем же мы оперировать со строковыми представлениями чисел! Проще вычислять такую таблицу. Даже не таблицу; понадобятся только 3 массива: для L(k,s), для L(k-1,s) и для R(k,s).
Упрощенная задача вроде бы решена. Теперь встает вопрос эффективного отсечения по границам диапазона. Вот тут пока глухо, как в танке... Не перебором же в самом деле...
Что-то V-Isa не подает голоса... Наверно, препод решил, что дал задачу не по зубам...  |
|
| Вернуться к началу |
|
|
GREA
Зарегистрирован: 14.05.2003
Сообщения: 758
Откуда: Новосибирск
|
| Добавлено: Вс Фев 22 2004 12:18 Заголовок сообщения: |
|
|
| Из далеких уголков моей памяти понемногу всплывет тот факт, что вроде подобная задача уже решалась у нас (только я тогда на паре отсутсвовал. Надо обратиться к конспектам (если найду, конечно. Давно это было) |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
