初級プログラミング

[初心者]

入力はｎ(正の整数)で、n=a^2+b^2となるa,bが
存在するときはa,bの組を一つ、しないときはNoを出力するんですが、やり方がまったくわかりません。
どなたかお願いします。
環境はLinux,gccです。

[box]

a, bに関する制約はないのですか？
仮に制約がないとすると、与式を満たす(a, b)の組は
無限に存在します。

[たいちう]

小さなnに対して、手で解いてみてください。
例えば、n=5について(a, b) = (1, 2)が言えますが、n=6については、Noになります。

0 < n <= 10 位までの全ての n について、手で解いて見ましょう。
特にNoという出力のためには、いきあたりばったりの方法ではだめで、
適切な手順で試してみて、条件を満たす(a, b)がないことを示さないといけません。

適切な手順を発見できたら、プログラムの出番です。
まずは発見しましょう。

> a, bに関する制約はないのですか？

私の説明では、これを勝手に整数と制約しています。

[tk-xleader]

実数の範囲でなら無数に存在しますね。
整数の範囲ということであれば、難しくなります。（解けなかった…）

[フリオ]

　
>入力はｎ(正の整数)で、n=a^2+b^2となるa,b

　"2乗の和"というのが、ヒントですね。
　
グラフで考えた方がわかりやすいかも。
　

[たかぎ]

確かにa, bがどんな値でもよいのかどうかを決めるのが先決です。
実数だけでなく、複素数まで考えるときりがありません。

[初心者]

すいませんa,bには正の整数という制約がありました。
a=1のときk=n-a^2としてb=1,2...に対してk=b^2となるbが見つかったらa,bを記憶させて、
なかったらa=2,3......
とかいっろいろやってみたんですがやはりうまくいきません(^^;
>フリオさん
どういうことですか？

[box]

> とかいっろいろやってみたんですがやはりうまくいきません

いろいろやってみたときのコードを提示するお考えはありますか？

[組木紙織]

作るのが(少し)大変な方法をしてる。。。

二重ループ使ったら簡単にできますよ。

[たかぎ]

追求すると後からいろいろ出てきそうなので、念のため確認します。

nに上限はありますか？
具体的には、unsigned intやunsigned longなどの組み込み型で表現できる範囲なのか、そうでないのかによって方針が変わります。
組み込み型で表現できる範囲に制限されないのであれば、多倍長演算が必要になります。

[lbfuvab]

一例として

#include<math.h>

unsigned int Search(unsigned int n,unsigned int *a,unsigned int *b){  //見つからなかったら0,見つかったら1
    unsigned int i,j,k,bFind=0;
    
    i=(unsigned int)ceil(sqrt(n));
    
    for(j=0;j<i;j++){
        for(k=0;k<i;k++){
            if(j*j+k*k == n){
                bFind=1;
                goto LOOP_END;
            }
        }
    }
    LOOP_END:;
    if(bFind){
        *a=j;
        *b=k;
    }
    return bFind;
}

とかですか。