Как сократить время работы программы

[dimon_snake]

Даётся число 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.

[min@y™]

Записываю числа в строковою, потом каждый символ превращаю в цифру

Убрать немедля!
Дальше не читал.

[min@y™]

Дочитал до этого места:

Но число может быть от 1 до 10^100.

Ты уверен?

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



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

Скачать всё.

[dimon_snake]

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

[Аватар]

Отож, полный перебор для твоего 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 код так оформлять это кибер-преступление. Прежде всего против самого себя Сам в нем через два дня ни чего не поймешь

[dimon_snake]

Сообщение от Аватар

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 это уж слишком долго.

[ViktorR]

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

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

Что то в голову пока не лезут мысли. Был сложный день
Как-то так, ...

[Аватар]

Наверно так: 78 = 77 + 1 = 66 + 12 ...
Как бы не очень число комбинаций

[ViktorR]

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

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

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



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

[min@y™]

А на чем написана программа?

какая программа?