2-21r · informatik.az

Найти все k-значные числа Армстронга (2<k<10).

К-значное число является числом Армстронга, если сумма к-ых степеней его цифр равна самому числу.

Например, 153=1^3 + 5^3 + 3^3, 8208=8^4 + 2^4 +8^4 являются числами Армстронга. Если k=3, то диапазон проверки чисел 100 – 999, если k=4, то 1000 – 9999.

В программе A2_21a в строке 7 нижняя граница чисел n1=10^(k-1). В цикле (строки 9 – 21) перебираются все к-значные числа и для каждого числа находится суммак-ых степеней его цифр – строка 15. Если эта сумма равна исходному числу (строка 20) число выводится на экран. Если в процессе вычисления суммы, она становится больше проверяемого числа, то дальше это число не проверяется (строка 17). Этим мы чуть-чуть уменьшаем общее время вычисления. Однако при к=8 и, особенно, при к=9, время вычисления достаточно большое (до десятка минут). Чтобы уменьшить время вычисления, к-ые степени цифр от 0 до 9 можно подсчитать заранее и сохранить их.

В программе A2_21b степени всех цифр подсчитывается заранее и сохраняются в массиве с (строки 7 -13). В строке 21 эти значения используются при вычислении суммы к-ых степеней цифр числа. Время вычисления при к=9 уменьшится (примерно в 4-5 раз), однако останется все таки большим (несколько минут). Дальнейшее уменьшение времени возможно специальным методом подсчета суммы.

Program A2_21a;

Var

k,n1,n,i,j,s,q,p:integer;

BEGIN

readln(k);

n1:=10;

for i:=1 to k-2 do n1:=n1*10;

for i:=n1 to n1*10 -1 do

begin

n:=i; s:=0;

while (n<>0) do

begin

q:=n mod 10; p:=q;

for j:=1 to k-1 do p:=p*q;

s:=s+p;

if (s>i) then break;

n:=n div 10;

end;

if (s=i) then writeln(i);

end;

readln;

END.

//Program A2.21a;

#include <iostream>

using namespace std;

int main()

{ int k,n1,n,i,j,s,q,p;

cin>>k;

n1=10;

for(i=1;i<k-1;i++) n1*=10;

for(i=n1;i<n1*10;i++)

{

n=i; s=0;

while (n)

{

q=p=n%10;

for(j=1;j<k;j++) p*=q;

s+=p;

if(s>i) break;

n/=10;

}

if(s==i)cout<<i<<endl;

}

return 0;

}

Program A2_21b;

Var

k,n1,n,i,j,s,q,p:integer;

c:array[0..9] of integer;

BEGIN

readln(k);

c[0]:=0; c[1]:=1;

for i:=2 to 9 do

begin

p:=i;

for j:=1 to k-1 do p:=p*i;

c[i]:=p;

end;

n1:=10;

for i:=1 to k-2 do n1:=n1*10;

for i:=n1 to n1*10 - 1 do

begin

n:=i; s:=0;

while (n<>0) do

begin

s:=s+c[n mod 10];

if (s>i) then break;

n:=n div 10;

end;

if (s=i) then writeln(i);

end;

readln;

END.

//Program A2.21b;

#include <iostream>

using namespace std;

int main()

{ int k,n1,n,i,j,s,q,p;

int c[10]={0,1};

cin>>k;

n1=10;

for(i=1;i<k-1;i++) n1*=10;

for(i=2;i<10;i++)

{ p=i;

for(j=1;j<k;j++) p*=i;

c[i]=p;

}

for(i=n1;i<n1*10;i++)

{

n=i; s=0;

while (n)

{

s+=c[n%10];

if(s>i) break;

n/=10;

}

if(s==i)cout<<i<<endl;

}

return 0;

}