主要是算法题练习记录……
兔子繁衍问题
设有一对新生的兔子，从第三个月开始他们每个月都生一对兔子，新生的兔子从第三个月开始又每个月生一对兔子。按此规律，并假定兔子没有死亡，每个月的兔子对数有多少？
- 分析
f(1) = 1 (第1个月有一对兔子）
f(2) = 1 (第2个月还是一对兔子）
f(3) = 2 (原来有一对兔子，第3个开始，每个月生一对兔子）
f(4) = 3 (原来有两对兔子，有一对可以生育）
f(5) = 5 (3个月出生的那对兔子也可以生育,现在有两对兔子可以生育）
f(6) = 8 (第4个月出生的那对兔子可以生育，现在有3对兔子可以生育）
……
f(n) = f(n-1) + f(n-2)
由上规律可言得出：
f(n) = f(n-1) + f(n-2)
基本就是一个简单的递归：
编程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
using namespace std;
int p(int n)
{
if(n==1 || n==2)
{
return 1;
}
else if(n>2)
{
return p(n-1)+p(n-2);
}
}
int main()
{
int n;
cin>>n;
cout<<p(n)<<endl;
}
|
整数分解问题
某些整数能分解成若干个连续整数和的形式，例如：
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
某些整数不能分解成连续整数和，例如：16
输入：一个整数
输出： 整数N对应的所有分解组合，若没有则输出None
- 分析：可以想到，分解的整数最大不会出超过 N/2+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
|
//将整数分成若干连续整数和
using namespace std;
int main()
{
int n,temp,flag=0;
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n/2+1;i++)
{
sum=0;
temp = i;
for(int j=i;j<=n/2+1;j++)
{
sum = sum + j ;
if(sum==n)
{
flag=1;
for(int k=temp;k<=j;k++)//输出每一种结果
{
cout<<k<<" ";
}
cout<<endl;
break;
}
}
}
if(flag==0)
{
cout<<"None"<<endl;
}
}
|
一个人的旅行
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。
输出草儿能去某个喜欢的城市的最短时间。
sample input：
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Output：
9
- 分析：
相当于多起点多终点，求最短的路径的问题，使用最短路径算法
假设相邻的城市就是出发起点，而想要去的地方就是多个终点。
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
using namespace std;
int line[index][index];
int dis[index];
int flag[index]={0};
int maxn;
void dijkstra()
{
for(int i=0;i<maxn;i++)
{
dis[i]=MAX;//初始化dis
}
dis[0]=0;//假设从第0个开始为起点，所以dis[0]到自己的距离为0
for(int i=0;i<=maxn;i++)
{
int temp=MAX;
int k;
for(int j=0;j<=maxn;j++)
{
if(!flag[j] && temp>dis[j])//如果没有加入集合，找到最短的加入集合
{
temp=dis[j];
k=j;
}
}
flag[k]=1; //设置加入集合 的为已访问
for(int m=0;m<=maxn;m++)
{
if(!flag[m]&& dis[m]>dis[k]+line[k][m])//找到是否经过一个点使得从原点到m距离更短
{
dis[m]= dis[k]+line[k][m];//更新
}
}
}
}
int main()
{
int T,S,D;
while(cin>>T>>S>>D)
{
for(int i=0;i<=index;i++)
{
for(int j=1;j<=index;j++)
{
line[i][j]=MAX;//初始
}
}
int a,b,c,t;
maxn=0;
for(int i=0;i<T;i++)
{
cin>>a>>b>>c;
maxn=max(max(maxn,a),b);
if(line[a][b]>c)//录入距离
{
line[a][b]=c;
line[b][a]=c;
}
}
for(int i=0;i<S;i++)//假设邻近距离家的距离为0
{
cin>>t;
line[0][t]=0;
line[t][0]=0;
}
dijkstra();
int min_dis=MAX;
for(int i=0;i<D;i++)
{
cin>>t;
min_dis=min(dis[t],min_dis);//获取最近的
}
cout<<min_dis<<endl;
}
return 0;
}
|