C言語 再帰の問題について

Question

前提・実現したいこと

この問題が解けずに困っています。
皆さんの知恵を貸してください。

カウンター魔法を得意とするパイザ君は、同じくカウンター魔法を使うモンスターと戦っています。バトルはターン制で、パイザ君が先攻で、パイザ君とモンスターで交互に魔法を使い合います。パイザ君の魔法は 1 回目と 2 回目に使うときにはダメージ 1 ですが、 3 回目以降の n 回目には、(モンスターから受けた (n - 1) 回目の攻撃のダメージ) + (モンスターから受けた (n - 2) 回目の攻撃のダメージ) のダメージを与えます。モンスターの魔法はこれよりも強力で、 1 回目と 2 回目には同じくダメージ 1 ですが、 3 回目以降の n 回目には、 (パイザ君から受けた (n - 1) 回目の攻撃のダメージ) * 2 + (パイザ君から受けた (n - 2) 回目の攻撃のダメージ) のダメージを与えます。

パイザ君は自分がどれくらいモンスターの攻撃を耐えられるか知りたいと思っています。パイザ君の体力を H として、両者が同じ魔法を使い続けたとき、モンスターの何回目の攻撃でパイザ君の体力が 0 以下になるかを出力してください。

入力される値
入力は以下のフォーマットで与えられます。

H

1 行目にパイザ君の体力を表す整数 H が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。

期待する出力
モンスターの何回目の攻撃でパイザ君の体力が 0 以下になるかを出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件
すべてのテストケースにおいて、以下の条件をみたします。

3 ≤ H ≤ 10^8

入力例1
7

出力例1
4

入力例2
35

出力例2
6

該当のソースコード

#include <stdio.h>
int damage (int n){
    int ans;
    if(n==1 || n==2 || n==3 || n==4){
        ans = 1;
    }
    if(n>=5 && n%2 ==1){
        ans = damage(n-1)+damage(n-3);
    }
    if(n>=5 && n%2 ==0){
        ans = damage(n-3)*damage(n-3)+damage(n-5);
    }
    return ans;
}
int main(void){
    int H;
    scanf("%d\n",&H);
    int cnt=0;
    for(int i=2;;i+=2){
        H-=damage(i);
        cnt++;
        if(H<=0){
            break;
        }
        
    }
    printf("%d\n",cnt);
    return 0;
}

Comments

[maisumakun]

名前からしてpaizaの問題のようですが、このような公開の場でアドバイスを求めていい部類のものなのでしょうか？

[tatsu99]

(パイザ君から受けた (n - 1) 回目の攻撃のダメージ) * 2
とは、２倍のように受け取れますが、
2乗の意味ですか。

[kater]

paizaのレベルアップ問題集という問題集からの問題になります。見出しに以下のように書かれていました。
”このコーナーでは、プログラミングスキルを伸ばしたい方向けに問題セットを用意しました。
プログラムを書けるようになるための一番の近道はたくさんコードを書くことです。
自分の実力や目的に合わせて問題を選び、レベルアップを目指しましょう。
なお、このコーナー内の問題については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
授業や研修にもご利用いただけますので、ぜひ教材などにもお使いください。”

[kater]

tatsu99さん
そこでミスをしていました！
解答ありがとうございました。

Answer 1

質問への追記・修正の依頼にて、tatsu99さんにコメントをいただき解決しました。
コードは以下のようになりました

#include <stdio.h>
int damage (int n){
    int ans;
    if(n==1 || n==2 || n==3 || n==4){
        ans = 1;
    }
    if(n>=5 && n%2 ==1){
        ans = damage(n-1)+damage(n-3);
    }
    if(n>=5 && n%2 ==0){
        ans = damage(n-3)*2+damage(n-5);
    }
    return ans;
}
int main(void){
    int H;
    scanf("%d\n",&H);
    int cnt=0;
    for(int i=2;;i+=2){
        H-=damage(i);
        cnt++;
        if(H<=0){
            break;
        }
        
    }
    printf("%d\n",cnt);
    return 0;
}