|
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; } |
Найти все 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 раз), однако останется все таки большим (несколько минут). Дальнейшее уменьшение времени возможно специальным методом подсчета суммы.
