当前位置:网站首页>P1028 calculation of number (recursive & recursive)

P1028 calculation of number (recursive & recursive)

2021-08-10 08:03:50 wx6110fa547fd20

P1028 The calculation of numbers ( recursive & Recurrence )

  Subject portal

Ideas : set up a[i] by n=i When the number of programs . Know when i There is a scheme for not operating , then i You can add... To the left of the 1,2,…… i / 2, Then it is transformed into solving a[1],a[2],……a[i/2] Number of alternatives . This is obviously a recursive process , Because each scheme is obtained by prefix and , So we can use an array to hold prefixes and . The recursive formula :a[ i ]=a[i-1]+(a[ i/2]+1)

Recursive writing :

#include<bits/stdc++.h>
using namespace std;
int b[1005],n;
int main(){
	cin>>n;
	for(int i=1;i<=n/2;i++)
	b[i]=b[i-1]+(b[i/2]+1); 
	cout<<b[n/2]+1<<endl;
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.

Recursive writing :

#include<bits/stdc++.h>
using namespace std;
int sum[1005],n;
int dfs(int x){
	if(x==1) return sum[x]=1;
	if(sum[x]) return sum[x];
	int ans=0;
	for(int i=1;i*2<=x;i++)
		 ans+=dfs(i);
	return sum[x]=ans+1;
} 
int main(){
	cin>>n;
	dfs(n);
	cout<<sum[n]<<endl;
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205505r.html