以下の問題を教えてください。よろしくお願いします。
ある数を一桁ずつに分け、それぞれの数字を自分と同じ数でべき
乗し足し合わせると元の数になるものを開き直り数としたとき
1以上の整数で開き直り数をすべて見つけるプログラミング
を知りたいです。
ただし0の0乗を0として扱います。
ex)3435は開き直り数 3^3+4^4+3^3+5^5=3435
学校の課題について
Re: 学校の課題について
Windows10 VisualStudio2019 clang
#include <stdio.h>
#include <stdlib.h>
unsigned long**RepeTbl[2]; /* 内部テーブル(2つの行列) */
unsigned long InitRepe(int n,int r)
{
unsigned long**a=RepeTbl[0],**b=RepeTbl[1]; int i,j;
if (a) { for (i=0;a[i];i++) free(a[i]); free(a); RepeTbl[0]=0; }
if (b) { for (i=0;b[i];i++) free(b[i]); free(b); RepeTbl[1]=0; }
if (r<0||n<=0) return 0;
RepeTbl[0]=a=(unsigned long**)malloc(sizeof*a*(r+1)); a[r]=0;
RepeTbl[1]=b=(unsigned long**)malloc(sizeof*b*(r+1)); b[r]=0;
if (r==0) return 1;
for (i=0;i<r;i++) a[i]=(unsigned long*)malloc(sizeof**a*n);
for (i=0;i<r;i++) b[i]=(unsigned long*)malloc(sizeof**b*n);
for (i=0;i<r;i++) a[i][n-1]=1;
for (j=1;j<n;j++) a[r-1][j]=1;
for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--)
a[i][j]=a[i][j+1]+a[i+1][j];
for (i=0;i<r;i++) a[i][0]=0;
for (i=0;i<r;i++) for (j=1;j<n;j++)
b[i][j-1]=a[i][j]+=a[i][j-1];
for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j];
if (n==1) for (i=0;i<r;i++) b[i][0]=1;
else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1;
for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1])
{ printf("InitRepe(%d,%d)overflow\n",n,r); exit(1); }
return b[0][n-1];
}
unsigned long RepeToNum(int*vec)
{
int i; unsigned long*p,num=0;
for (i=0;(p=RepeTbl[0][i])!=0;i++) num+=p[vec[i]];
return num;
}
void NumToRepe(unsigned long num,int*vec)
{
int i,j=0; unsigned long*p;
for (i=0;(p=RepeTbl[1][i])!=0;i++) {
while (p[j]<=num) j++;
num-=RepeTbl[0][i][j]; vec[i]=j;
}
}
int main(void)
{
int i,vec[10],num[10],su[10],j;
unsigned long ans,k,wk,tm,rui[10],cz[10],bnd=InitRepe(10,10);
for (i=0;i<=9;i++)
{ rui[i]=i; for (j=1;j<i;j++) rui[i]*=i; }
cz[0]=1;
for (i=1;i<=9;i++) cz[i]=cz[i-1]*10;
for (k=1;k<bnd;k++) {
NumToRepe(k,vec);
for (i=0;i<=9;i++) num[i]=0;
for (i=0;i<=9;i++) num[vec[i]]++;
for (ans=i=0;i<=9;i++) ans+=rui[i]*num[i];
for (i=0;i<=9;i++) su[i]=0;
for (wk=ans,i=9;i>=0;i--) {
for (tm=cz[i],j=0;wk>=tm;j++,wk-=tm) ;
if (su[j]++>=num[j]) { ans=0; break; }
}
if (ans) for (i=1;i<=9;i++)
if (su[i]!=num[i]) { ans=0; break; }
if (ans) printf("%lu\n",ans);
}
return 0;
}
Re: 学校の課題について
「すべて見つける」ということなので、何も考えないと無限に探索しないといけません。
そこで、まず探索範囲を見積もります。
おそらく、どこかで桁数を増やせば増やすほどもとの数の方が大きくなり、
操作結果が追いつかなくなるでしょう。
当然9をいっぱい使うほうが操作結果が大きくなるため、
9を並べた数とその操作結果を調べてみます。
9を10個並べた時、もとの数の方が操作結果より大きくなりました。
よって、きちんと証明はしていませんが、10桁以下の数だけ調べればよさそうです。
また、この結果より、任意の10桁以下の数について、
操作結果は3874204890より大きくならないことがわかります。
この値なら、32ビット符号なし整数に収まりそうです。 (符号付きだとダメです)
あとは、単純に探索していきましょう。
現代のPCであれば、数分もあれば終わるはずです。
再帰は、累乗の計算に用います。
aのb乗は、bが偶数のとき(a×a)の(b÷2)乗、
bが奇数のとき((a×a)の((b-1)÷2)乗)×a、と表すことができる性質を用います。
ただし、毎回計算するのは効率が悪いので、
最初に各数字の累乗を配列に格納しておきます。
おまけ:出てきた数をOEIS(オンライン整数列大辞典)に入れて検索した結果
A046253 - OEIS
そこで、まず探索範囲を見積もります。
おそらく、どこかで桁数を増やせば増やすほどもとの数の方が大きくなり、
操作結果が追いつかなくなるでしょう。
当然9をいっぱい使うほうが操作結果が大きくなるため、
9を並べた数とその操作結果を調べてみます。
9を10個並べた時、もとの数の方が操作結果より大きくなりました。
よって、きちんと証明はしていませんが、10桁以下の数だけ調べればよさそうです。
また、この結果より、任意の10桁以下の数について、
操作結果は3874204890より大きくならないことがわかります。
この値なら、32ビット符号なし整数に収まりそうです。 (符号付きだとダメです)
あとは、単純に探索していきましょう。
現代のPCであれば、数分もあれば終わるはずです。
再帰は、累乗の計算に用います。
aのb乗は、bが偶数のとき(a×a)の(b÷2)乗、
bが奇数のとき((a×a)の((b-1)÷2)乗)×a、と表すことができる性質を用います。
ただし、毎回計算するのは効率が悪いので、
最初に各数字の累乗を配列に格納しておきます。
#include <stdio.h>
unsigned int ruizyo(unsigned int a, unsigned int b) {
if (b == 0) {
if (a == 0) return 0; else return 1;
} else if (b == 1) {
return a;
} else if (b % 2 == 0) {
return ruizyo(a * a, b / 2);
} else {
return a * ruizyo(a * a, (b - 1) / 2);
}
}
int main(void) {
const unsigned int MAX = 4000000000u;
unsigned int i;
unsigned int r[10];
for (i = 0; i < 10; i++) {
r[i] = ruizyo(i, i);
}
for (i = 1; i < MAX; i++) {
unsigned int sum = 0;
unsigned int value;
for (value = i; value > 0; value /= 10) {
sum += r[value % 10];
}
if (sum == i) {
printf("%u\n", i);
}
}
return 0;
}
A046253 - OEIS
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 学校の課題について
まず「3435は開き直り数」という例が出ているのに、100以下というのは、探索範囲が明らかに全然足りなくてダメです。コケ さんが書きました: ↑3年前上記のようにnumを100以下に設定してもうまくいきません
さらに、探索する過程で、外側のループのカウンタである変数numの値を破壊してしまうのもダメです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
-
- 記事: 48
- 登録日時: 7年前
Re: 学校の課題について
//自分なりに書いてみました。
#include<stdio.h>
#include<math.h>
int GetNDigit(int N,int D)
{
//指定の桁を取り出す関数(変数Dが0で1の位
return N/((int)pow(10.0,(double)D))%10;
}
int MyMadePow(int a,int b)
{
//DOMAIN ERRORが出るので自作の累乗関数を書きました。
if(a==0 && b==0) return 0;
if(a!=0 && b==0) return 1;
int c=1;
for(int i=1;i<=b;i++)
{
c*=a;
}
return c;
}
long int HirakiNaori(long int a)
{
//開き直り数の判定をする関数
//3435
long int N=0;//変数Nは加算するので0に初期化
long int j;
long int i;
for(i=0;i<10;i++)
{
j=MyMadePow(GetNDigit(a,i),GetNDigit(a,i));
//DOMAIN ERRORで苦しんだので自作累乗関数を利用
//printf("a=%d i=%d ",a,i);
N+=j;
}
if(N==a) return N;
return -1;
}
int main()
{
//printf("%d",GetNDigit(3435,3));
for(long int i=0;i<900000000;i++)
{
if(HirakiNaori(i)!=-1) //判定関数が-1じゃなければ開き直り数
printf("%d ",HirakiNaori(i));
//printf("%d ",MyMadePow(3,3));
}
return 0;
}