|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
30.01.2016, 14:00 | #1 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Как сократить время работы программы
Даётся число n. Нужно вывести количество пар чисел, сумма которых будет равна числу n, и сумма цифр которых будет равняться сумме цифр числа n.
Например, число 11. Пары, которые подходят: 11 0 0 11 1 10 10 1. Значит, ответ 4, т.к. 4 пары. Я делал так: делаю цикл от 1 до n, и перебираю варианты: 0 и n, 1 и n-1, 2 и n-2, и т.д. Записываю числа в строковую, потом каждый символ превращаю в цифру и помещаю в массив. В массиве подсчитываю сумму элементов. Проверяю, sum=sum1+sum2 или нет. И считаю кол-во вариантов. Но число может быть от 1 до 10^100. И при больших числах слишком долго выполняется цикл, а потом и в longint не влезает. Подскажите, как еще можно реализовать это задание? Код:
Последний раз редактировалось dimon_snake; 30.01.2016 в 22:05. |
30.01.2016, 17:41 | #2 | |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Цитата:
Дальше не читал. Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
|
30.01.2016, 21:27 | #3 | |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Дочитал до этого места:
Цитата:
Я провёл эксперимент - написал тестовую программу, чтобы хотя бы примерно оценить время выполнения. Причём без применения строковых преобразований - только операции над числами. Смотри и делай выводы. Имхо, число итераций брутфорса будет расти экспоненциально при добавлении каждого десятичного разряда к исходному числу. Так что для больших чисел брутфорс неприемлем, надо искать какой-то другой способ. Скачать всё. Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
|
30.01.2016, 21:40 | #4 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
В том и дело, что нужно использовать какой-то другой алгоритм.
Число в сотой степени, там скорее всего нужно через строковый файл прочитать, подсчитать сумму цифр. А дальше не знаю. Но точно до 10^100. Просто алгоритм попроще найти нужно. А на чем написана программа? Последний раз редактировалось dimon_snake; 30.01.2016 в 21:52. |
30.01.2016, 21:45 | #5 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Отож, полный перебор для твоего 10^ого-го точно не прокатит. Нужно как-то проанализировать поведение этих чисел и тогда прогу делать на основе этого анализа. Выяснить закономерности поведения. Вот хотя-бы такие
1. Для любой суммы цифр числа существует минимально число с такой суммой: 15 - 69 34 - 7999 и т.д. 2. Максимального нет, поскольку справа любое количество нулей можно добавить 3. Пример поведения для 15 69, 69+9=78, 78+9=87, 87+9=96, 96+9=а тут ломается закономерность. Эта. Но дальше другая есть. 4. Возможно для суммы s искать пары с 1 и s-1, 2 и s-2, 3 и s-3 ... Может это и не поможет, не копал. А может и какой-то рекуррентный способ есть. Но не полный перебор PS код так оформлять это кибер-преступление. Прежде всего против самого себя Сам в нем через два дня ни чего не поймешь
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 30.01.2016 в 21:56. |
30.01.2016, 22:06 | #6 | |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Цитата:
|
|
30.01.2016, 22:13 | #7 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,318
|
Правильно ли я понял задачу?
Пусть есть число: abcde - буквы - это цифры числа. парой могут быть числа вида: abcd0 и e; abc00 и de и т.д., а так же: a-1bcd0 и 1000e, a-2bcd0 и 2000e или такие: abcd1 и e-1. Сумма этих чисел равна исходному числу, а сумма всех цифр пары равна сумме цифр исходного числа. Другие комбинации не видятся. Если это так, то возможно, что тут следует использовать комбинаторику и просто вычислить число комбинаций, а не заниматься перебором? Что то в голову пока не лезут мысли. Был сложный день Как-то так, ...
Как-то так, ...
|
30.01.2016, 22:16 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Наверно так: 78 = 77 + 1 = 66 + 12 ...
Как бы не очень число комбинаций
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
30.01.2016, 22:41 | #9 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,318
|
78 - две цифры.
Пара 70 и 08 подходят. Т.о первая цифра меняется от 0 до 7, а вторая от нуля до 8. По первой цифре имеем 8 пар (вторые цифры которых не меняются - тут имеется ввиду то, что у второго числа есть лидирующий ноль), а по второй 9. Вроде как 72 пары уже есть. Интересно, а сколько в реальности? PS: Попытался скачать программу от min@y™, но мой 7z ругается на то, что не поддерживает формат упаковки exe-шника, а распакованная программа не запускается - Это не приложение для Win Как-то так, ...
Как-то так, ...
Последний раз редактировалось ViktorR; 30.01.2016 в 22:50. |
30.01.2016, 23:25 | #10 | |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Цитата:
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
как уменьшить время работы программы | 22hope22 | C# (си шарп) | 9 | 26.05.2013 21:41 |
VS 2010 - как поменять текст у кнопки во время работы программы, из .cpp файла? | MrRockchip | Общие вопросы C/C++ | 3 | 21.02.2011 22:44 |
Как сократить время выполнения макроса? | Алексей11111 | Microsoft Office Excel | 11 | 01.12.2009 20:04 |
Как узнать время работы программы в паскаль? | bullvinkle | Помощь студентам | 2 | 26.12.2008 11:20 |
Как сократить время? МАКРОС! | jungo | Microsoft Office Excel | 17 | 01.05.2008 12:13 |