Длинная целочисленная арифметика, вычислить сумму ряда

@Roma567 · Регистрация: 27.12.2021

Студворк — интернет-сервис помощи студентам

Задание: вычислить сумму первых N членов следующего ряда:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \sum_{k=1}^{n}k^k<br />$

Никак не могу сделать это задание. Преподаватель говорит, что задание сделано неправильно.
Если поможете, буду очень благодарен.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
Procedure Equel(Var s1,s2:string;Var l:integer);
Var i,l1,l2:integer;
begin
   l1:=Length(s1);
   l2:=Length(s2);
   If l1>l2 then begin
               l:=l1;
               For i:=1 to l-l2 do s2:='0'+s2
            end
            else begin
               l:=l2;
               For i:=1 to l-l1 do s1:='0'+s1
            end
end;
 
Function Plus(a,b:string):string;
Var i,k,l:integer;
    x,x1,x2:integer;
    s,c:string;
    p:boolean;
begin
    Equel(a,b,l);
    p:=False;
    s:=' ';
    For i:=l Downto 1 do
    begin
   Val(a[i],x1,k);
   Val(b[i],x2,k);
   x:=x1+x2;If p then x:=x+1;
   If x>10 then p:=True else p:=False;
   x:=x mod 10;
   Str(x,c);
   s:=c+s
end;
If p then s:='1'+s;
Plus:=s
end;
 
Function MultiOne(a:string;b:integer):string;
Var i,j:integer;
    s,s1:string;
    x:integer;
begin
    s:='';
    For i:=Length(a) Downto 1 do begin
       x:=StrToInt(a[i]);
       x:=x*b;
       s1:=IntToStr(x);
       For  j:=1 to (Length(a)-i) do s1:=s1+'0';
       s:=Plus(s,s1)
    end;
    MultiOne:=s
end;
 
 
Function Multi(a,b:string):string;
Var i,j:integer;
    s1,s:string;    
begin
    s:='';
    For i:=Length(b) Downto 1 do begin
      s1:=MultiOne(a,StrToInt(b[i]));
      For j:=1 to (Length(b)-i) do s1:=s1+'0';
      s:=Plus(s,s1)
    end;
    Multi:=s
end;
 
 
Var a, b, s:string;
    k, n:integer;
Begin
    write('число n: ');
    readln(n);
    a := '0';
    b := a;
    For k := 1 to n do 
    begin
      s := (Power(k, k)).ToString;
      a := Plus(a, s.ToString);
     // writeln(k, '  ', a);
     end;  
    writeln();
    writeln('Сумма = ',a);
End.

@thyrex · 27.04.2022, 07:03

Судя по меткам нужна программа под PABC.NET. Почему тогда не пользуетесь типом BigInteger?

@bormant · 27.04.2022, 08:02

задание сделано неправильно

k^k считается не в длинной арифметике, весь смысл теряется.

Уточните, что является целью задания: реализация длинной арифметики вручную или просто вычисление результата. Во втором случае, как вам правильно заметили выше, закат солнца вручную не обязателен, достаточно будет встроенной в PascalABC.NET длинной арифметики.

@Roma567 · 27.04.2022, 13:00 **[ТС]**

bormant, препод хочет именно через string. Всё условие, которое он нам дал, в задании. Объяснений никаких не даёт, кроме того каким должен быть вывод.

@mr-Crocodile · 27.04.2022, 13:33

Сообщение от Roma567

препод хочет именно через string.

ну так выкинь своё

Сообщение от Roma567

Pascal
1
(Power(k, k))

и реализуй возведение в степень через операцию умножения

только скачала сделай нормальную функцию умножения длинных чисел.

потому что твоя работает неверно:

Pascal
1
    WriteLn(Multi('12','12'));

Code
1
9000

@JuriiMW · 02.05.2022, 07:27

У вас, Roma567, то val, то toString, то IntToStr), нужно уж определиться: то-ли на TP писать, то-ли на PABC.NET

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~

Давайте попробуем написать данную программу:

Для начала нужно разбить задачу на несколько более мелких.
Можно сначала сделать сложение длинных чисел.
Попробуем написать такую функцию, на вход которой будем подавать два числа в виде строки, а получать строку-сумму этих чисел.

Pascal
1
2
3
4
function Add(a, b : String) : String ;
begin
 
end;

Наверное будет проще, если результат будет уже такой длины, как максимальное из исходных чисел:

Pascal
1
2
3
4
5
function Add(a, b : String) : String ;
begin
  Result := '0'*Max(a.Length, b.Length);
 
end;

Теперь нам понадобятся:
переменная для хранения переноса, если он вдруг случится,
ну и указатели на текущий символ каждой из строк a, b и Result,
которые изначально указывают на конец каждого из чисел — самый младший разряд,
т.к. начинаем складывать мы с младшего разряда, а он в конце строки.

Pascal
1
2
3
4
5
6
function Add(a, b : String) : String ;
begin
  Result := '0'*Max(a.Length, b.Length);
  var(d, ai, bi, ri) := (0, a.Length, b.Length, Result.Length);
 
end;

Впишем само сложение:

Pascal
5
6
7
8
9
10
11
12
13
14
15
16
17
  while (ai>0) or (bi>0) do
    begin
      if ai>0 then
        begin
          d+=ToInt(a[ai]); ai-=1;
        end;
      if bi>0 then
        begin
          d+=ToInt(b[bi]); bi-=1;
        end;
      Result[ri]:=ToChr(d); ri-=1;
      d:=d div 10;
    end;

В переменной переноса d может остаться значение, которое нужно дописать слева:

Pascal
18
  if d>0 then Result:=ToChr(d)+Result;

В коде появились какие-то ToInt и ToChr.
Это две функции. Первая превращает символ в целое число.
А вторая наоборот целое число в символ, но с маленькой фишкой:
число берётся не целиком, а только его младшая цифра.
Это упрощает основной код и позволяет избавить его от некоторых лишних действий.

Вот полученный код:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function ToChr(n : Integer) := (n mod 10).ToString[1];
function ToInt(c : Char) := StrToInt(c);
 
function Add(a, b : String) : String ;
begin
  Result := '0'*Max(a.Length, b.Length);
  var(d, ai, bi, ri) := (0, a.Length, b.Length, Result.Length);
  while (ai>0) or (bi>0) do
    begin
      if ai>0 then
        begin
          d+=ToInt(a[ai]); ai-=1;
        end;
      if bi>0 then
        begin
          d+=ToInt(b[bi]); bi-=1;
        end;
      Result[ri]:=ToChr(d); ri-=1;
      d:=d div 10;
    end;
  if d>0 then Result:=ToChr(d)+Result;
end;
 
begin
  Add('1', '2').Println;
  Add('123', '456').Println;
  Add('123', '999').Println;
  Add('321', '999').Println;
end.

Как видите, я сразу написал несколько контрольных тестов, которые легко посчитать в уме, но дающие увидеть правильность исполнения алгоритма.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~

Сложение не вызвало ни каких проблем.

Теперь напишем умножение:

Pascal
1
2
3
4
function Mul(a, b : String) : String;
begin
 
end;

Когда мы умножаем два многозначных числа в столбик, то производим несколько действий по нахождению промежуточных значений, которые в итоге складываем. К примеру:

Code
1
2
3
4
5
6
7
  12
 х34
 ---
  48
 36
 ---
 408

Т.е. выполняем отдельные действия:
1) 12·4=48
2) 12·3=36
3) 48+360=408
Обратили внимание на третье действие? Сдвиг разряда как умножение на 10.
А если начать считать сначала, а не с конца второго числа?
1) 12·3=36
2) 36·10=360
3) 12·4=48
4) 360+48=408
Получается примерно так:

Pascal
1
2
3
4
5
6
function Mul(a, b : String) : String;
begin
  Result := ToStr(0);
  foreach var bi in b do
    Result := Add( Mul10(Result), MulChr(a, bi) );
end;

Сначала результат равен 0.
А для каждой цифры второго числа слева направо выполняем три действия:
— домножить результат на 10 (если число не 0, то тупо приписать ему нолик справа)
— умножить число a на очередную цифру из b
— сложить полученные два числа

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function ToStr(n : Integer) := n.ToString;
function ToChr(n : Integer) := (n mod 10).ToString[1];
function ToInt(c : Char) := StrToInt(c);
 
function Add(a, b : String) : String ;
begin
  Result := '0'*Max(a.Length, b.Length);
  var(d, ai, bi, ri) := (0, a.Length, b.Length, Result.Length);
  while (ai>0) or (bi>0) do
    begin
      if ai>0 then
        begin
          d+=ToInt(a[ai]); ai-=1;
        end;
      if bi>0 then
        begin
          d+=ToInt(b[bi]); bi-=1;
        end;
      Result[ri]:=ToChr(d); ri-=1;
      d:=d div 10;
    end;
  if d>0 then Result:=ToChr(d)+Result;
end;
 
function Mul10(a : String) : String := a = '0' ? a : a + '0';
 
function MulChr(a : String; c : Char) : String;
begin
  var(d, n) := (0, ToInt(c));
  Result := '0'*a.Length;
  for var i := a.Length downto 1 do
    begin
      d += ToInt(a[i]) * n;
      Result[i] := ToChr(d);
      d := d div 10;
    end;
  if d>0 then Result:=ToChr(d)+Result;
end;
 
function Mul(a, b : String) : String;
begin
  Result := ToStr(0);
  foreach var bi in b do
    Result := Add( Mul10(Result), MulChr(a, bi) );
end;
 
begin
  Mul('10', '11').Println;
  Mul('11', '11').Println;
  Mul('123', '345').Println; // 42435
  Mul('99999', '77777').Println; // 7777622223
end.

Вот и предыдущий код по сложению нам пригодился.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~

Осталось возведение в степень.

Воспользуемся формулой быстрого возведения в степень:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function ToStr(n : Integer) := n.ToString;
function ToChr(n : Integer) := (n mod 10).ToString[1];
function ToInt(c : Char) := StrToInt(c);
 
function Add(a, b : String) : String ;
begin
  Result := '0'*Max(a.Length, b.Length);
  var(d, ai, bi, ri) := (0, a.Length, b.Length, Result.Length);
  while (ai>0) or (bi>0) do
    begin
      if ai>0 then
        begin
          d+=ToInt(a[ai]); ai-=1;
        end;
      if bi>0 then
        begin
          d+=ToInt(b[bi]); bi-=1;
        end;
      Result[ri]:=ToChr(d); ri-=1;
      d:=d div 10;
    end;
  if d>0 then Result:=ToChr(d)+Result;
end;
 
function Mul10(a : String) : String := a = '0' ? a : a + '0';
 
function MulChr(a : String; c : Char) : String;
begin
  var(d, n) := (0, ToInt(c));
  Result := '0'*a.Length;
  for var i := a.Length downto 1 do
    begin
      d += ToInt(a[i]) * n;
      Result[i] := ToChr(d);
      d := d div 10;
    end;
  if d>0 then Result:=ToChr(d)+Result;
end;
 
function Mul(a, b : String) : String;
begin
  Result := ToStr(0);
  foreach var bi in b do
    Result := Add( Mul10(Result), MulChr(a, bi) );
end;
 
procedure Div2(var a : String);
begin
  var d := 0;
  for var i := 1 to a.Length do
    begin
      d:=d*10 + ToInt(a[i]);
      a[i]:=ToChr(d shr 1);
      d:=d and 1;
    end;
  a:=a.TrimStart('0');
end;
 
function Pow(a, b : String) : String;
begin
  var r := ToStr(1);
  while b.Length > 0 do
    begin
      if '13579'.Contains(b.Last) then
        r := Mul(r, a);
      a := Mul(a, a);
      Div2(b);
    end;
  Result := r;
end;
 
begin
  Pow('123','123').Println;
end.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~

Для нахождения результата по условиям задания? нужно основную программу переписать так:

Pascal
72
73
74
75
76
77
78
begin
  var n := ReadInteger;
  var s := ToStr(0);
  for var k := 1 to n do
    s := Add(s, Pow(ToStr(k), ToStr(k)) );
  s.Println;
end.

Запустим и проверим, скажем для 4:

1¹=1
2²=4
3³=27
4⁴=256
----
1+4+27+256=288

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	27.04.2022, 07:03
	Судя по меткам нужна программа под PABC.NET. Почему тогда не пользуетесь типом BigInteger? 0

@Roma567 0 / 0 / 0 Регистрация: 27.12.2021 Сообщений: 11
	27.04.2022, 13:00 [ТС]
	bormant, препод хочет именно через string. Всё условие, которое он нам дал, в задании. Объяснений никаких не даёт, кроме того каким должен быть вывод. 0

Длинная целочисленная арифметика, вычислить сумму ряда

Решение