Найти сумму первых 100 элементов упорядоченной последовательности - Free Pascal
Формулировка задачи:
Помогите с олимпиадной задачей! Эта программа выводит в ответе нули. Я не могу понять, чего не хватает. Подскажите, что именно и где прописать.
Последовательность натуральных чисел от 1 до М упорядочена по возрастанию суммы цифр в десятичном представлении чисел (при одинаковой сумме цифр больший порядковый номер имеет большее число).
Для сумма первых 100 элементов упорядоченной последовательности составит …
Программа на языке Pascal для реализации данного упорядочения может выглядеть, например, так:
В результате расчетов получим, что сумма первых 100 элементов упорядоченной последовательности из 1000 чисел составит 16430.
Program Sort_number;
function Digit(Num:longint;N:integer): integer;
var tmp,i:longint;
begin
tmp:=Num;
for i:=1 to N do tmp:=tmp div 10;
Digit:=tmp mod 10;
end;
function Sum_Digits( Num:integer):integer;
var N_Digits,i,Sum:integer;
begin
if (Num<10)then N_Digits:=1
else
N_Digits:=trunc(ln(Num+0.0)/ln(10.0)+1.01)+1;
Sum:=0;
for i:=0 to N_Digits-1 do
Sum:=Sum+Digit(Num,i);
Sum_digits:=Sum;
end;
var Sequence:array[0..1005]of integer;
Number,Count,i,Imin,tmp,Target,ok,Sum:integer;
begin
val(paramstr(1),Number,ok);
val(paramstr(2),Target,ok);
for Count:=0 to Number do Sequence[Count]:=Count;
for Count:=0 to Number-1 do begin
Imin:=Count;
for i:=Count to Number do
if(Sum_Digits(Sequence[i])<Sum_Digits(Sequence[Imin]))then Imin:=i
else if(Sum_Digits(Sequence[i])=Sum_Digits(Sequence[Imin])) then
if(Sequence[i]<Sequence[Imin]) then Imin:=i;
tmp:=Sequence[Imin];Sequence[Imin]:=Sequence[Count];Sequence[Count]:=tmp;
end;
Sum:=0;
for i:=0 to Target do Sum:=Sum+Sequence[i];
writeln('Sum of first ',Target,'is ',Sum);
readln;
end.Решение задачи: «Найти сумму первых 100 элементов упорядоченной последовательности»
textual
Листинг программы
const mm=1000; function DigSum(n: Longint): Integer; begin Result:=0; while n>0 do begin Inc(Result,n mod 10); n:=n div 10; end; end; procedure Sort(var a: array of Longint; m: Integer); var s: array [0..mm-1] of Integer; i, l, r, nn: Longint; function Less(j, k: Integer): Boolean; begin Result:=(s[j]<s[k]) or (s[j]=s[k]) and (a[j]<a[k]); end; procedure Swap(j, k: Integer); var ta: Longint; ts: Integer; begin nn:=i; ta:=a[j]; a[j]:=a[k]; a[k]:=ta; ts:=s[j]; s[j]:=s[k]; s[k]:=ts; end; begin for i:=0 to m-1 do s[i]:=DigSum(a[i]); nn:=0; l:=0; r:=m-1; while l<r do begin l:=nn; for i:=l to r-1 do if Less(i+1,i) then Swap(i+1,i); r:=nn; for i:=r downto l+1 do if Less(i,i-1) then Swap(i,i-1); end; end; var a: array [1..mm] of Longint; m, n, i, s: Longint; begin Read(m,n); for i:=1 to m do a[i]:=i; Sort(a,m); for i:=1 to n do Inc(s,a[i]); WriteLn(s); end.
Объяснение кода листинга программы
- В функции DigSum(n: Longint): Integer; происходит вычисление суммы цифр числа n.
- В процедуре Sort(var a: array of Longint; m: Integer); происходит сортировка массива a по возрастанию.
- В функции Less(j, k: Integer): Boolean; определяется условие для сравнения элементов массива a.
- В процедуре Swap(j, k: Integer); происходит обмен элементов a[j] и a[k], а также соответствующих им элементов массива s.
- В основной части программы считываются значения m и n, заполняется массив a значениями от 1 до m, затем вызывается процедура Sort для сортировки массива a.
- Далее суммируются элементы отсортированного массива a с помощью цикла for i:=1 to n do Inc(s,a[i]);
- И наконец, выводится на экран значение переменной s.