题目1：
问题描述
有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
例如，长度为4的地面一共有如下5种铺法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
输入格式
只有一个数N，代表地板的长度
输出格式
输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
using namespace std;
int fun(int n)
{
if(n==1) return 1;
if(n==2) return 2;
else
return fun(n-1)+fun(n-2);
}
int main()
{
int n;
cin>>n;
cout<<fun(n);
return 0;
}
|
题目：
问题描述
如果一个序列满足下面的性质，我们就将它称为摆动序列：
1. 序列中的所有数都是不大于k的正整数；
2. 序列中至少有两个数。
3. 序列中的数两两不相等；
4. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。
比如，当k = 3时，有下面几个这样的序列：
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
一共有8种，给定k，请求出满足上面要求的序列的个数。
输入格式
输入包含了一个整数k。（k<=20）
输出格式
输出一个整数，表示满足要求的序列个数。
样例输入
3
样例输出
8
使用全排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<iostream>
#include<set>
#include<sstream>
#define maxn 20
using namespace std;
set<string> se[maxn];
void is2(string &s,int i)
{
stringstream ss;
ss<<i;
ss>>s;
}
bool issuccess(string str)
{
for(int i=2;i<str.length();i++)
{
if((str[i-1]>str[i-2]&&str[i]>str[i-2])||(str[i-1]<str[i-2]&&str[i]<str[i-2]))
return false;
}
return true;
}
void per(string s,int n,int k)
{
if(k>=n)
{
for(int i=3;i<=n;i++)
{
string s2=s.substr(0,i);
if(issuccess(s2))
se[i].insert(s2);
}
}
else
for(int i=k;i<n;i++)
{
swap(s[i],s[k]);
per(s,n,k+1);
swap(s[i],s[k]);
}
}
int main()
{
int k,sum=0;
cin>>k;
string s1;
for(int i=1;i<=k;i++)
{
string s2;
is2(s2,i);
s1=s1+s2;
}
per(s1,k,0);
for(int i=3;i<=k;i++)
sum+=se[i].size();
cout<<k*(k-1)+sum;
return 0;
}
|
使用dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int sum,n;
int data[1000]={0},book[1000]={0};
void bfs(int t){
if(t>1){
if(t==2){
sum++;
}
else if((data[t-2]-data[t-3])*(data[t-1]-data[t-3])<0){
sum++;
}
else return ;
}
for(int i = 1;i <= n;i++){
if(book[i]==0){
data[t] = i;
book[i] = 1;
bfs(t+1);
book[i] = 0;
}
}
return ;
}
int main(){
sum=0;
scanf("%d",&n);
bfs(0);
printf("%d\n",sum);
return 0;
}
|
题目：用dfs将1到n的全排列输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int book[1000]={0},data[1000]={0};
int n;
void dfs(int t)
{
if(t==n)
{
for(int i=0;i<n;i++)
cout<<data[i];
cout<<endl;
}
for(int i=1;i<=n;i++)
{
if(book[i]==0)
{
data[t]=i;
book[i]=1;
dfs(t+1);
book[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
|
题目：（分治递归）
任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=210 +28 +25 +2+1
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
输入格式
输入包含一个正整数N（N<=20000），为要求分解的整数。
输出格式
程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include<algorithm>
using namespace std;
void divide(int n)
{
int i;
for(i=20;i>=0;i--)
{
if(n&(1<<i))
break;
}
cout<<"2";
if(i==0||i==2)
cout<<"("<<i<<")";
if(i!=1&&i!=2&&i!=0)
{
cout<<"(";
divide(i);
cout<<")";
}
if(n-(1<<i))
{
printf("+");
divide(n-(1<<i));
}
}
int main()
{
int n;
cin>>n;
divide(n);
}
|
题目：
最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
不妨设
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。
输入格式
仅有一个数：N<201。
输出格式
请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。
样例输入
3
样例输出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<iostream>
using namespace std;
void printAn(int k,int n)
{
if(n+1==k)
{
return ;
}
cout<<"sin("<<k;
if(k!=n)
{
if(k%2!=0)
cout<<"-";
else
cout<<"+";
}
printAn(k+1,n);
cout<<")";
}
void printSn(int n)
{
for(int i=1;i<n;i++)
cout<<"(";
for(int i=1;i<=n;i++)
{
if(i!=n)
{
printAn(1,i);
cout<<"+"<<n-i+1;
cout<<")";
}
else
{
printAn(1,i);
cout<<"+"<<n-i+1;
}
}
}
int main()
{
int n;
cin>>n;
printSn(n);
}
|