任意多倍長整数演算の問題

質問

任意多倍長整数演算を行う。

int f1 ( int x , y ) {

if (x == 1 ) return ( x + y );
return ( f1 ( x - 2 , y - 1 ) * 2 );
}
１）　f1の停止する範囲を求め、その範囲で停止することを証明せよ。

２）　１）の範囲で、f1 ( ｘ　、ｙ )　の値をｘ、ｙと整数定数を元にして四則演算を用いた式で表せるか。具体的にあらわしてそれが正しいことを示すか、表せないことを示せ。

以上の問題が解けません。
どなたか、解答方法などを教えていただけないでしょうか。

回答No.4

arrysthmia

おや、どっか違った？

回答No.3

arrysthmia

濃厚なカテ違いの香りが…

a の b 乗を pow(a, b) と書くとすれば、
f1(x,y) の値は、(y - (x-3)/2) * pow(2, (x-1)/2) かな。
Cプログラムなら、(y - x/2 - 1) * (int)(pow(2, x/2) + 0.01)
というか、(y - x/2 - 1) * (1 << x/2) なんだろうけれども。

効率は度外視して、再帰処理のデモとして書くならば、
停止性に配慮して、

int f1(int x , y){
　　int value;

　　if (x > 1) value = f1(x - 2, y - 1) * 2;
　　else if (x = = 1) value = x + y;
　　else /* エラー処理 */　;
　　return value;
}

とか？

補足

arrysthmia様
アドバイスありがとうございます。

少し違う感じがしますが、わざわざ回答ありがとうございます。

回答No.2

Tacosan

1: 逆. 「x が 2の倍数」の場合には x から何回 2 を引いても 1 になるはずないので停止しない. もちろんもともと x が負のときにも停止しない.
2: ん? 「x の y乗」をどのように表すんでしょうか? 「x^y」とかければいいけど, これは「四則演算」には入りませんよね.

補足

Tacosan様
アドバイスありがとうございます。

１）　すいません逆でした。。。そこまではだいたい読み取れるのですがその先が分かりませんし、それをどのように証明するかも検討がつかない状態です。

２）　四則演算ではないですが「x^y」も使えるということでお願いいたします。

回答No.1

Tacosan

1 は
「f1(x, y) が停止する」 iff 「x = 1」または「f1(x-2, y-1) が停止する」
だから簡単じゃね?
2 は表せないと思う. そもそも四則演算しか使えないとべき乗が表現できないし.

補足

Tacosan様
アドバイスありがとうございます。

１）ですが、僕の勉強不足だと思うのですがわかりません。。。
　　問題を見たところｘが２の倍数でないと、永遠ループすると思うのですけど
　　どうなのでしょうか？

２）ですが、べき乗に関してですが使えます。
　　おそらく２は表せるのでしょうか？