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