寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例

アルゴ式(beta版)の「設計技法とデータ構造 (#毎日アルゴ式)」再帰からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例

僕が作成、提出したコードは、以下のとおりです。

Q4-1. 1 + 2 + … + N (再帰)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-1. 1 + 2 + … + N (再帰)
https://algo-method.com/tasks/422
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int func(int n){
    if(n==0){
        return 0;
    }else{
        return func(n-1)+n;
    }
}
int main(void){
    int n;
    cin>>n;
    cout<<func(n)<<endl;
    return 0;
}
・Q4-2. A + (A+1) + … + B (再帰)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-2. A + (A+1) + … + B (再帰)
https://algo-method.com/tasks/426
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int func(int n){
    if(n==0){
        return 0;
    }else{
        return func(n-1)+n;
    }
}
int main(void){
    int a,b;
    cin>>a>>b;
    cout<<func(b)-func(a-1)<<endl;
    return 0;
}
・Q4-3. フィボナッチ数列 (再帰-1)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-3. フィボナッチ数列 (再帰-1)
https://algo-method.com/tasks/425
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int func(int n){
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else{
        return func(n-1)+func(n-2);
    }
}
int main(void){
    int n;
    cin>>n;
    cout<<func(n)<<endl;
    return 0;
}
・Q4-4. フィボナッチ数列 (再帰-2)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-4. フィボナッチ数列 (再帰-2)
https://algo-method.com/tasks/423
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> fib(90,-1);
ll func(ll n){
    if(fib[n]!=-1){
        return fib[n];
    }else{
        fib[n]=func(n-1)+func(n-2);
        return fib[n];
    }
}
int main(void){
    ll n;
    cin>>n;
    fib[0]=0;
    fib[1]=1;
    cout<<func(n)<<endl;
    return 0;
}
・Q4-5. 部分和問題 (再帰-1)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-5. 部分和問題 (再帰-1)
https://algo-method.com/tasks/427
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
bool func(int i,int j){
    if(i==0){
        if(j==0){
            return true;
        }else{
            return false;
        }
    }else{
        bool tf=false;
        if(j>=a[i-1] && func(i-1,j-a[i-1])){
            tf=true;
        }else if(func(i-1,j)){
            tf=true;
        }
        return tf;
    }
}
int main(void){
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        int A;
        cin>>A;
        a.push_back(A);
    }
    if(func(n,x)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・Q4-6. 部分和問題 (再帰-2)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-6. 部分和問題 (再帰-2)
https://algo-method.com/tasks/438
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool func(ll i,ll j,vector<ll> a,vector<vector<ll>>& vv){
    if(i==0){
        if(j==0){
            return true;
        }else{
            return false;
        }
    }else{
        bool tf=false;
        if(j-a[i]>=0){
            if(vv[i-1][j-a[i]]==-1){
                vv[i-1][j-a[i]]=func(i-1,j-a[i],a,vv);
            }
            if(vv[i-1][j-a[i]]==1){
                tf=true;
            }
        }
        if(vv[i-1][j]==-1){
            vv[i-1][j]=func(i-1,j,a,vv);
        }
        if(vv[i-1][j]==1){
            tf=true;
        }
        return tf;
    }
}
int main(void){
    ll n,x;
    cin>>n>>x;
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<vector<ll>> vv(n+1,vector<ll>(x+1,-1));
    vv[0][0]=1;
    if(func(n,x,a,vv)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・Q4-7. 数を選ぶ (1)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-7. 数を選ぶ (1)
https://algo-method.com/tasks/428
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> func(int n,int l,int r){
    vector<vector<int>> ans;
    if(l>r){
        return ans;
    }else if(n==0){
        vector<int> v;
        ans.push_back(v);
        return ans;
    }else{
        vector<vector<int>> vv=func(n-1,l,r);
        for(auto i : vv){
            i.push_back(l);
            ans.push_back(i);
        }
        vector<vector<int>> vv2=func(n,l+1,r);
        for(auto i : vv2){
            ans.push_back(i);
        }
        return ans;
    }
}
int main(void){
    int n,l,r;
    cin>>n>>l>>r;
    vector<vector<int>> ans=func(n,l,r);
    for(auto i : ans){
        for(int j=i.size()-1;j>=0;j--){
            cout<<i[j]<<((j==0) ? "\n" : " ");
        }
    }
    return 0;
}
・Q4-8. 数を選ぶ (2)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-8. 数を選ぶ (2)
https://algo-method.com/tasks/430
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int ans=0;
void f(int x,int y){
    if(y==n){
        ans++;
        return;
    }
    for(int i=x+1;i<=r;i++){
        f(i,y+1);
    }
}
int main(void){
    cin>>n>>l>>r;
    for(int i=l;i<=r;i++){
        f(i,1);
    }
    cout<<ans<<endl;
    return 0;
}
・Q4-9. 昇順数

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」再帰の解答例
Q4-9. 昇順数
https://algo-method.com/tasks/429
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<string> func(ll n,char l,char r){
    if(l>r){
        return {};
    }else if(n==0){
        return {""};
    }else{
        vector<string> ans;
        for(auto& i : func(n-1,l,r)){
            i.insert(i.begin(),l);
            ans.push_back(i);
        }
        for(auto& i : func(n,l+1,r)){
            ans.push_back(i);
        }
        return ans;
    }
}
int main(void){
    ll l,r;
    cin>>l>>r;
    ll sum=0;
    for(int i=1;i<=9;i++){
        auto vs=func(i,'1','9');
        if(stoi(vs.front())>r){
            break;
        }
        for(string& s : vs){
            int j=stoi(s);
            if(j>r){
                break;
            }
            if(j>=l){
                sum+=j;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com