プログラマ専用SNS ミクプラ

以下の問題を教えてください。よろしくお願いします。

ある数を一桁ずつに分け、それぞれの数字を自分と同じ数でべき

乗し足し合わせると元の数になるものを開き直り数としたとき

1以上の整数で開き直り数をすべて見つけるプログラミング

を知りたいです。

ただし0の0乗を0として扱います。

ex)3435は開き直り数　3^3+4^4+3^3+5^5=3435

丸投げはダメだと思い追記します

コード:

#include <stdio.h>
#include <math.h>

intmain (void)
{
  int num;
  int dig;
  int sum=0;
  for (num = 1; num<100; num++)
    {
    	while(num)
    	{
        	dig=num%10;
        	sum=sum+pow(dig,dig);
        	num=num/10;
        }
        if(sum==num)
        {
        	printf("%d",sum);
        }
    }
  return 0;
}

上記のようにnumを100以下に設定してもうまくいきません

Windows10　　　VisualStudio2019　　　　clang

コード:

#include <stdio.h>
#include <stdlib.h>

unsigned long**RepeTbl[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;
}

VisualStudio2019 clang 10 で実行

コード:

c:\b>clang-cl c1.c

c:\b>c1.exe
1
3435
438579088

c:\b>

http://www001.upp.so-net.ne.jp/isaku/pu ... wer.c.html

質問者です。
できれば再帰を用いていただきたいです。
結構複雑でもっと簡略化はできないものなのでしょうか

「すべて見つける」ということなので、何も考えないと無限に探索しないといけません。
そこで、まず探索範囲を見積もります。
おそらく、どこかで桁数を増やせば増やすほどもとの数の方が大きくなり、
操作結果が追いつかなくなるでしょう。
当然9をいっぱい使うほうが操作結果が大きくなるため、
9を並べた数とその操作結果を調べてみます。

コード:

         数    操作結果
  999999999  3486784401
 9999999999  3874204890
99999999999  4261625379

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;
}

おまけ：出てきた数をOEIS(オンライン整数列大辞典)に入れて検索した結果
A046253 - OEIS

コケさんが書きました: ↑
4年前
上記のようにnumを100以下に設定してもうまくいきません

まず「3435は開き直り数」という例が出ているのに、100以下というのは、探索範囲が明らかに全然足りなくてダメです。
さらに、探索する過程で、外側のループのカウンタである変数numの値を破壊してしまうのもダメです。

コード:

//自分なりに書いてみました。
#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;
}

プログラマ専用SNS ミクプラ

学校の課題について

学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について

Re: 学校の課題について