|
Найти все 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 раз), однако останется все таки большим (несколько минут). Дальнейшее уменьшение времени возможно специальным методом подсчета суммы.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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;
}
|
|
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
|
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;
}
|
|
