3乗の和で表せる数

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Tatsu
記事: 4
登録日時: 10年前

3乗の和で表せる数

#1

投稿記事 by Tatsu » 10年前

独学でC言語を勉強しており、下記の課題を解いてみましたが、もっと効率のいいアルゴリズムはありますでしょうか?

アルゴリズム的には、a,b,c,dの変数をひたすらforで回して調べている感じですが、わざわざ4回もループを作る必要があるのか疑問です。。。

課題
10000未満の正の整数を考える。このとき、ある2つの正の整数の3乗の和として表す表し方が異なる数で2通りある数を全て求めなさい。

コード:

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

int main()
{
    
    int a=0, b=0, c=0, d=0;
    int x = 0, y = 0;
    
    printf("hello\n");
    
    do{
        for(d=1; d<22; d++){
            for(c=d+1; c<22; c++){
                for(b=1; b<22; b++){
                    for(a=b+1; a<22; a++){
                        x = a*a*a + b*b*b;
                        y = c*c*c + d*d*d;
                        if(x == y && a != c && a < c){
                            printf("%d = %d^3 + %d^3 = %d^3 + %d^3\n", x, a, b, c, d);
                        }
                    }
                }
            }
        }
        printf("bye\n");

    }while(x < 10000);
    
    return 0;
}
出力結果

hello
1729 = 10^3 + 9^3 = 12^3 + 1^3
4104 = 15^3 + 9^3 = 16^3 + 2^3
bye

かずま

Re: 3乗の和で表せる数

#2

投稿記事 by かずま » 10年前

コード:

                for(b=1; b<22; b++){
                    for(a=b+1; a<22; a++){

コード:

                for(b=d+1; b<22; b++){
                    for(a=c-1; a>b; a--){
にすると、x, y の計算回数が 44100から 5985に減少します。

Tatsu
記事: 4
登録日時: 10年前

Re: 3乗の和で表せる数

#3

投稿記事 by Tatsu » 10年前

ありがとうございます!!

かずま

Re: 3乗の和で表せる数

#4

投稿記事 by かずま » 10年前

y = c*c*c + d*d*d; を for(b=d+1; b<22; b++){ の直前の移すと、
y の計算回数は 210 になります。

かずま

Re: 3乗の和で表せる数

#5

投稿記事 by かずま » 10年前

コード:

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

int main()
{
    int a = 0, b = 0, c = 0, d = 0;
    int x = 0, y = 0;
    int nx = 0, ny = 0;

    printf("hello\n");
    for (d = 1; d < 22; d++) {
        for (c = d + 1; c < 22; c++) {
            y = c*c*c + d*d*d;
            ny++;
            if (y > 10000) break;
            for (b = d + 1; b < 22; b++) {
                for (a = b + 1; a < c; a++) {
                    x = a*a*a + b*b*b;
                    nx++;
                    if (x > y) break;
                    if (x == y) {
                        printf("%d = %d^3 + %d^3 = %d^3 + %d^3\n", x, a, b, c, d);
                    }
                }
            }
        }
    }
    printf("bye\n", nx, ny);
    printf("nx=%d, ny=%d\n", nx, ny);
    return 0;
}
実行結果

コード:

hello
1729 = 10^3 + 9^3 = 12^3 + 1^3
4104 = 15^3 + 9^3 = 16^3 + 2^3
bye
nx=5515, ny=198

アバター
usao
記事: 1887
登録日時: 11年前

Re: 3乗の和で表せる数

#6

投稿記事 by usao » 10年前

内側のループはこんな感じで探索できないかな?

コード:

    int Cubic[22];
    for( int i=0; i<22; i++ ){	Cubic[i] = i*i*i;	}

    ...

    //※aとbのループは省略.
    //常に a<b であるものとする.
    const int a = 9;
    const int b = 10;
    const int AB = Cubic[a] + Cubic[b];

    //cとdの探索.c<d とする.
    int c=1;
    int d=21;
    while( c<d )
    {
        if( c==a ){ ++c;    continue;   }
        if( d==b ){ --d;    continue;   }

        const int CD = Cubic[c] + Cubic[d];
        if( CD == AB )
        {
            std::cout << "c=" << c << ", d=" << d << std::endl;
            break;
        }
        else if( CD < AB )
        {   ++c;    }
        else
        {   --d;    }
    }
#あら, (a,b)と(c,d)が元コードと逆ですね…

たいちう
記事: 418
登録日時: 13年前

Re: 3乗の和で表せる数

#7

投稿記事 by たいちう » 10年前

> 内側のループはこんな感じで探索できないかな?

できないと思いますよ。
c=d=1から少しずつ増やしていくやりかたなら、
探索を軽くできると思うけど。

ちょっと時間がないので反証は探せないし、
少しずつ増やしていくやり方も今は作れないのが申し訳ないです。
そのうち時間ができたら作りますが誰か作ってくれまいか。

10000未満に限るならば、探索は軽くならないだろうし、
反証は存在しないかもしれません。
かずまさんが3乗の計算を毎回しているのも、これが理由でしょうか。

えび
記事: 1
登録日時: 10年前

Re: 3乗の和で表せる数

#8

投稿記事 by えび » 10年前

コード:

#include <stdio.h>

int main() {
	int prePow[22], i, a, b, tmp;
	struct SumResult {
		int cnt;  /* 組み合わせの数 */
		int n[4]; /* 組み合わせる異なる正数 */
	} sum[10000]; /* 10,000までの和についての情報を記録 */

	for(i=1; i<22; i++) { prePow[i] = i*i*i; } /* 事前に1^3から21^3を配列に格納しておく */
	for(i=9; i<10000; i++) { sum[i].cnt = 0; } /* カウント用の変数を初期化 */

	// 常に a < b の関係
	for(a=1; a<21; a++) {
		for(b=a+1; b<22; b++) {
			tmp = prePow[a]+prePow[b]; /* a^3 + b^3 を計算 */
			if(tmp>=10000) break;      /* 和が10,000以上なら無視 */
			if(sum[tmp].cnt<2) {       /* これまでに同じ和となった組み合わせの数を調べる */
				sum[tmp].n[sum[tmp].cnt*2  ] = a;
				sum[tmp].n[sum[tmp].cnt*2+1] = b;
			}
			sum[tmp].cnt++; /* カウンタを1加算する */
		}
	}

	printf("hello\n");
	for(i=9; i<10000; i++) {
		if(sum[i].cnt==2) { /* 見つかった組み合わせの数が2通りの和を探す */
			printf("%d = %d^3 + %d^3 = %d^3 + %d^3\n", i, sum[i].n[0], sum[i].n[1], sum[i].n[2], sum[i].n[3]);
		}
	}
	printf("bye\n");
	return 0;
}
初投稿です。皆さんどうぞよろしくお願いします。
考えたアルゴリズムを簡単にコーディングしてみました。
=== アルゴリズム ===
  1. 事前に1^3から21^3まで求めて配列に格納しておく
  2. 2重ループで異なる正数の3乗 a^3 と b^3 の和を求める
  3. これまでに同じ和が見つかった回数を調べる
  4. 2回未満だった場合は aとbを記録しカウンタを進める
  5. シングルループでカウンタを10,000通り調べる
  6. カウンタが2のものについてだけ結果を表示する
メモリちょっとだけ喰うのが難点でしょうか・・・
// 10000「未満」を「以下」と勘違いしてたので修正
// 小手先の速さのためにループ開始をi=9(=1^3+2^3)からに変更

閉鎖

“C言語何でも質問掲示板” へ戻る