Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Delphi > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 30.01.2016, 15:00   #1
dimon_snake
Форумчанин
 
Регистрация: 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 не влезает.
Подскажите, как еще можно реализовать это задание?
Код:
var
a,a1,a2:array[1..100]of byte; \3 массива, первый для n, второй и третий нужны при перебирании чисел
fi,fo:text;
i,n,n1,n2,k,sum,i1,i2,l,sum1,sum2:longint;
x,y,z:longint;
s,s1,s2:string;
begin
Assign(fi,'sequence.in');
Assign(fo,'sequence.out');
Reset(fi);
Rewrite(fo);
Read(fi,x);=читает число n (у меня x)
Str(x,s);\преобразуем его в строку
n:=length(s);
l:=0;
for i:=1 to 100 do a[i]:=0; \элементы первого массива обнуляем, на всякий случай
for i:=1 to n do val(copy(s,i,1),a[i],k); \число x по цифрам кидаем в массив
for i:=1 to n do sum:=sum+a[i];\считаем сумму цифр числа x
y:=0; 
z:=x;
for i:=1 to x do
   begin \вот этот цикл слишком долго идет при больших числах
      for i1:=1 to 100 do a1[i1]:=0;
      for i2:=1 to 100 do a2[i2]:=0;\обнуляем массив 2 и 3, т.к. при новом проходе через цикл они буду заполнены
      Inc(y); 
      Dec(z);
      sum1:=0;
      sum2:=0;
      Str(y,s1);
      n1:=length(s1);
      Str(z,s2);
      n2:=length(s2);
      for i1:=1 to n1 do val(copy(s1,i1,1),a1[i1],k);
      for i2:=1 to n2 do val(copy(s2,i2,1),a2[i2],k);
      for i1:=1 to n1 do sum1:=sum1+a1[i1];
      for i2:=1 to n2 do sum2:=sum2+a2[i2]; \считаем сумму цифр первого и второго числа для проверки
      if (sum1+sum2=sum)then
         begin \проверяем, подходит ли условие
             Inc(l);\наращиваем счетчик
         end;
      if (sum1+sum2=sum)and(y=z) \это на случай, к примеру, для 20. То есть бывает 0 20 и 20 0, две пары. А с 10 10 и 10 10 аналогично, просто не видно, что их меняют местами
      then Inc(l);
   end;
Inc(l); \Программа посчитает x 0, а 0 x не посчитает. 
Write(fo,l);
Close(fo);
end.

Последний раз редактировалось dimon_snake; 30.01.2016 в 23:05.
dimon_snake вне форума   Ответить с цитированием
Старый 30.01.2016, 18:41   #2
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,664
По умолчанию

Цитата:
Записываю числа в строковою, потом каждый символ превращаю в цифру
Убрать немедля!
Дальше не читал.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума   Ответить с цитированием
Старый 30.01.2016, 22:27   #3
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,664
По умолчанию

Дочитал до этого места:
Цитата:
Но число может быть от 1 до 10^100.
Ты уверен?

Я провёл эксперимент - написал тестовую программу, чтобы хотя бы примерно оценить время выполнения. Причём без применения строковых преобразований - только операции над числами. Смотри и делай выводы.



Имхо, число итераций брутфорса будет расти экспоненциально при добавлении каждого десятичного разряда к исходному числу. Так что для больших чисел брутфорс неприемлем, надо искать какой-то другой способ.

Скачать всё.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума   Ответить с цитированием
Старый 30.01.2016, 22:40   #4
dimon_snake
Форумчанин
 
Регистрация: 05.11.2015
Сообщений: 167
По умолчанию

В том и дело, что нужно использовать какой-то другой алгоритм.
Число в сотой степени, там скорее всего нужно через строковый файл прочитать, подсчитать сумму цифр. А дальше не знаю. Но точно до 10^100. Просто алгоритм попроще найти нужно.
А на чем написана программа?

Последний раз редактировалось dimon_snake; 30.01.2016 в 22:52.
dimon_snake вне форума   Ответить с цитированием
Старый 30.01.2016, 22:45   #5
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,052
По умолчанию

Отож, полный перебор для твоего 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 в 22:56.
Аватар на форуме   Ответить с цитированием
Старый 30.01.2016, 23:06   #6
dimon_snake
Форумчанин
 
Регистрация: 05.11.2015
Сообщений: 167
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
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 ...
Тоже вариант, но проверять все последовательности до 10^100 это уж слишком долго.
dimon_snake вне форума   Ответить с цитированием
Старый 30.01.2016, 23:13   #7
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,381
По умолчанию

Правильно ли я понял задачу?
Пусть есть число: abcde - буквы - это цифры числа.
парой могут быть числа вида:
abcd0 и e;
abc00 и de и т.д.,
а так же:
a-1bcd0 и 1000e,
a-2bcd0 и 2000e
или такие: abcd1 и e-1.
Сумма этих чисел равна исходному числу, а сумма всех цифр пары равна сумме цифр исходного числа.
Другие комбинации не видятся.

Если это так, то возможно, что тут следует использовать комбинаторику и просто вычислить число комбинаций, а не заниматься перебором?

Что то в голову пока не лезут мысли. Был сложный день
Как-то так, ...
ViktorR вне форума   Ответить с цитированием
Старый 30.01.2016, 23:16   #8
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,052
По умолчанию

Наверно так: 78 = 77 + 1 = 66 + 12 ...
Как бы не очень число комбинаций
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар на форуме   Ответить с цитированием
Старый 30.01.2016, 23:41   #9
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,381
По умолчанию

78 - две цифры.
Пара 70 и 08 подходят. Т.о первая цифра меняется от 0 до 7, а вторая от нуля до 8.
По первой цифре имеем 8 пар (вторые цифры которых не меняются - тут имеется ввиду то, что у второго числа есть лидирующий ноль), а по второй 9. Вроде как 72 пары уже есть.

Интересно, а сколько в реальности?

PS: Попытался скачать программу от min@y™, но мой 7z ругается на то, что не поддерживает формат упаковки exe-шника, а распакованная программа не запускается - Это не приложение для Win



Как-то так, ...

Последний раз редактировалось ViktorR; 30.01.2016 в 23:50.
ViktorR вне форума   Ответить с цитированием
Старый 31.01.2016, 00:25   #10
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,664
По умолчанию

Цитата:
А на чем написана программа?
какая программа?
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как уменьшить время работы программы 22hope22 C# (си шарп) 9 26.05.2013 21:41
VS 2010 - как поменять текст у кнопки во время работы программы, из .cpp файла? MrRockchip Общие вопросы C/C++ 3 21.02.2011 23:44
Как сократить время выполнения макроса? Алексей11111 Microsoft Office Excel 11 01.12.2009 21:04
Как узнать время работы программы в паскаль? bullvinkle Помощь студентам 2 26.12.2008 12:20
Как сократить время? МАКРОС! jungo Microsoft Office Excel 17 01.05.2008 12:13


12:49.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.