Liczba Armstronga to taka liczba naturalna, n-cyfrowa, której suma cyfr podniesionych do potęgi n jest równa tej liczbie:
np. \(\displaystyle{ 153 = 1 ^{3} + 5 ^{3} + 3 ^{3}}\)
Mam zadanie (C++) - aby wypisać (w kilka sekund!) wszystkie liczby Armstronga z zakresu <1, 2147483647>. Jako, że liczba ta jest dość duża - napisany przeze mnie program działa godzinami. Szukam liczb Armstronga metodą Brute-Force. Jednakże jest inna metoda. Podobno z kombinatoryki. Proszę o pomoc.
(chodzi o to, żeby nie trzeba było liczyć po kolei od 1 do ..., bo tak powtarzają się obliczenia: np. 123 i 321 dają taki sam wynik obliczeń).
PS.
Moje pytanie to: Ile zbiorów, w których elementy mogą się powtarzać, można ułożyć ze zbioru {1,2,3,4,5,6,7,8,9,0} - zbiory mają być kolejno: 1,2,3,4,5,6,7,8,9 i 10-elementowe. Czyli, że np. {1,1,1}, {1,2,3} ale już nie {3,2,1}
PS2. Czyli:
Zbiorów 2-el. z powtórzeniami ze zbioru {1,2,3,4,5,6,7,8,9,0} jest:
1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9
2,0 2,2 2,3 2,4 2,5 2,6 2,7 2,8 2,9
3,0 3,3 ...
...
9,9
czyli razem:
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55
PS3.
Ok, już wiem, to będzie kombinacja z powtórzeniami, której wzór to:
\(\displaystyle{ {k + n - 1 \choose k}}\)
Liczby Armstronga - algorytm
-
kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Liczby Armstronga - algorytm
Według mnie wzór na ilość zbiorów n- elementowych (od 1 do 10) z 10 cyfr z powtórzeniami to:
\(\displaystyle{ \sum_{n=1}^{10} {10+n-1 \choose n}}\)
Sprawdź to.
\(\displaystyle{ \sum_{n=1}^{10} {10+n-1 \choose n}}\)
Sprawdź to.
Liczby Armstronga - algorytm
mój działa pół minuty, ale kod jest dość rozbudowany, aby przyspieszyć program zminimalizowałam liczbę obliczeń, umieszczając obliczenia potęgowania i sumowania w tablicach:
Kod: Zaznacz cały
#include <iostream>
using namespace std;
main()
{
int tbpot[10][10],tbmn[10][10];
unsigned i,j;
for(i=0,j=0;j<=9;j++) tbpot[i][j]=j;
for(i=1,j=0;j<=9;j++) tbpot[i][j]=j*j;
for(i=2,j=0;j<=9;j++) tbpot[i][j]=j*j*j;
for(i=3,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j;
for(i=4,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j;
for(i=5,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j*j;
for(i=6,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j*j*j;
for(i=7,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j*j*j*j;
for(i=8,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j*j*j*j*j;
for(i=9,j=0;j<=9;j++) tbpot[i][j]=j*j*j*j*j*j*j*j*j*j;
for(i=0,j=0;j<=9;j++) tbmn[i][j]=j;
for(i=1,j=0;j<=9;j++) tbmn[i][j]=j*10;
for(i=2,j=0;j<=9;j++) tbmn[i][j]=j*100;
for(i=3,j=0;j<=9;j++) tbmn[i][j]=j*1000;
for(i=4,j=0;j<=9;j++) tbmn[i][j]=j*10000;
for(i=5,j=0;j<=9;j++) tbmn[i][j]=j*100000;
for(i=6,j=0;j<=9;j++) tbmn[i][j]=j*1000000;
for(i=7,j=0;j<=9;j++) tbmn[i][j]=j*10000000;
for(i=8,j=0;j<=9;j++) tbmn[i][j]=j*100000000;
for(i=9,j=0;j<=9;j++) tbmn[i][j]=j*1000000000;
unsigned j1,j2,j3,j4,j5,j6,j7,j8,j9,j10;
for(j1=1;j1<=9;++j1) {
if((tbpot[0][j1])==(tbmn[0][j1]))
cout<<tbpot[0][j1]<<endl;
}
for(j2=1;j2<=9;++j2){
for(j1=0;j1<=9;++j1) {
if((tbpot[2-1][j1]+tbpot[2-1][j2])==(tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[2-1][j1]+tbpot[2-1][j2]<<endl;
}
}
for(j3=1;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[2][j1]+tbpot[2][j2]+tbpot[2][j3])==(tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[2][j1]+tbpot[2][j2]+tbpot[2][j3]<<endl;
}
}
}
for(j4=1;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[3][j1]+tbpot[3][j2]+tbpot[3][j3]+tbpot[3][j4])==(tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[3][j1]+tbpot[3][j2]+tbpot[3][j3]+tbpot[3][j4]<<endl;
}
}
}
}
for(j5=1;j5<=9;++j5){
for(j4=0;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[4][j1]+tbpot[4][j2]+tbpot[4][j3]+tbpot[4][j4]+tbpot[4][j5])==(tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[4][j1]+tbpot[4][j2]+tbpot[4][j3]+tbpot[4][j4]+tbpot[4][j5]<<endl;
}
}
}
}
}
for(j6=1;j6<=9;++j6){
for(j5=0;j5<=9;++j5){
for(j4=0;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[5][j1]+tbpot[5][j2]+tbpot[5][j3]+tbpot[5][j4]+tbpot[5][j5]+tbpot[5][j6])==(tbmn[5][j6]+tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[5][j1]+tbpot[5][j2]+tbpot[5][j3]+tbpot[5][j4]+tbpot[5][j5]+tbpot[5][j6]<<endl;
}
}
}
}
}
}
for(j7=1;j7<=9;++j7){
for(j6=0;j6<=9;++j6){
for(j5=0;j5<=9;++j5){
for(j4=0;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[6][j1]+tbpot[6][j2]+tbpot[6][j3]+tbpot[6][j4]+tbpot[6][j5]+tbpot[6][j6]+tbpot[6][j7])
==(tbmn[6][j7]+tbmn[5][j6]+tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[6][j1]+tbpot[6][j2]+tbpot[6][j3]+tbpot[6][j4]+tbpot[6][j5]+tbpot[6][j6]+tbpot[6][j7]<<endl;
}
}
}
}
}
}
}
for(j8=1;j8<=9;++j8){
for(j7=0;j7<=9;++j7){
for(j6=0;j6<=9;++j6){
for(j5=0;j5<=9;++j5){
for(j4=0;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[7][j1]+tbpot[7][j2]+tbpot[7][j3]+tbpot[7][j4]+tbpot[7][j5]+tbpot[7][j6]+tbpot[7][j7]+tbpot[7][j8])
==(tbmn[7][j8]+tbmn[6][j7]+tbmn[5][j6]+tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[7][j1]+tbpot[7][j2]+tbpot[7][j3]+tbpot[7][j4]+tbpot[7][j5]+tbpot[7][j6]+tbpot[7][j7]+tbpot[7][j8]<<endl;
}
}
}
}
}
}
}
}
for(j9=1;j9<=9;++j9){
for(j8=0;j8<=9;++j8){
for(j7=0;j7<=9;++j7){
for(j6=0;j6<=9;++j6){
for(j5=0;j5<=9;++j5){
for(j4=0;j4<=9;++j4){
for(j3=0;j3<=9;++j3){
for(j2=0;j2<=9;++j2){
for(j1=0;j1<=9;++j1){
if((tbpot[8][j1]+tbpot[8][j2]+tbpot[8][j3]+tbpot[8][j4]+tbpot[8][j5]+tbpot[8][j6]+tbpot[8][j7]+tbpot[8][j8]+tbpot[8][j9])
==(tbmn[8][j9]+tbmn[7][j8]+tbmn[6][j7]+tbmn[5][j6]+tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[8][j1]+tbpot[8][j2]+tbpot[8][j3]+tbpot[8][j4]+tbpot[8][j5]+tbpot[8][j6]+tbpot[8][j7]+tbpot[8][j8]+tbpot[8][j9]<<endl;
}
}
}
}
}
}
}
}
}
for(j10=1;j10<=2;++j9){
for(j9=0;j9<=1;++j9){
for(j8=0;j8<=4;++j8){
for(j7=0;j7<=7;++j7){
for(j6=0;j6<=4;++j6){
for(j5=0;j5<=8;++j5){
for(j4=0;j4<=3;++j4){
for(j3=0;j3<=6;++j3){
for(j2=0;j2<=4;++j2){
for(j1=0;j1<=8;++j1){
if((tbpot[9][j1]+tbpot[9][j2]+tbpot[9][j3]+tbpot[9][j4]+tbpot[9][j5]+tbpot[9][j6]+tbpot[9][j7]+tbpot[9][j8]+tbpot[9][j9]+tbpot[9][j10])
==(tbmn[9][j10]+tbmn[8][j9]+tbmn[7][j8]+tbmn[6][j7]+tbmn[5][j6]+tbmn[4][j5]+tbmn[3][j4]+tbmn[2][j3]+tbmn[1][j2]+tbmn[0][j1]))
cout<<tbpot[9][j1]+tbpot[9][j2]+tbpot[9][j3]+tbpot[9][j4]+tbpot[9][j5]+tbpot[9][j6]+tbpot[9][j7]+tbpot[9][j8]+tbpot[9][j9]+tbpot[9][j10]<<endl;
}
}
}
}
}
}
}
}
}
}
cin.get();
}
Ostatnio zmieniony 25 gru 2011, o 12:40 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Kod w [code][\code]!
Powód: Kod w [code][\code]!
-
Grzesio_
- Użytkownik
- Posty: 44
- Rejestracja: 23 gru 2011, o 22:59
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 3 razy
Liczby Armstronga - algorytm
żarcik w języku C
a tak działa:
Kod: Zaznacz cały
char*O41=
"!#!$!%!&!'!(!)!*!+!#^!%}!%~!&E!3W!z:!#*s!(@b!,e(!,hv!aLK!$1"
"E7!'7q[!.32.!.AaW!@a<E!@a<F!#3/5%!#{/`A!(?6\\L!)/PL>!.5&[_!";
main(O42,O)
{
if( !042 != O )
for(O42=O=0; O42+001<' '; O42++)
{
O=main(O,'-'-'-'); // :-\
return! O;
}
else
{
while( *(O41+ ++ O42) != 041 )
{
O = O*']' + O42[O41] - 042;%>
printf("%d\n", O);<%
}
return O42;
}
}Liczby Armstronga - algorytm
Super, ale nie rozumiem na jakiej zasadzie działa:)-- 31 gru 2011, o 12:16 --Świetne, już częsc kodu rozszyfrowałam i teraz myślę nad kluczem do O41. Fajny pomysł:)