数据结构作业题目 = =
前情回顾：矩阵转置-简单代码
一个简单的约瑟夫环代码
动态链表的课后作业。直接上代码：
READ MORE →
矩阵转置-简单代码
利用数组对两个矩阵进行转置。附上简单代码：
READ MORE →
HDOJ2045：不容易系列之(3)—— LELE的RPG难题——递推求解
Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即”可乐”）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
以上就是著名的RPG难题.
如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?
Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0=4是才能用。
f[1]=k; f[2]=k*(k-1); f[3]=k*(k-1)*(k-2);
如果n很大的会话，可以利用矩阵乘法快速幂进行加速。
可以参考Matrix67的博客
代码：
#include
int main()
{
_int64 i, t = 1, j, n[52];
n[1] = 3;
n[2] = n[3] = 1;
for (i = 4; i
HDOJ：阶乘取余
一道关于递推的题目，题目链接在这里
READ MORE →
HDOJ2044：一只小蜜蜂…——递推求解
Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。
Input
输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。
Output
对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。
Sample Input
2
1 2
3 6
Sample Output
1
3
递推求解，注意_int64。
代码：
#include
int main()
{
int a, b, n, i;
_int64 cell[52] = { 1, 1, 2 };
for (i = 3; i
HDOJ1465：不容易系列之一——递推求解
Problem Description
大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！
做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。
话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。
不幸的是，这种小概率事件又发生了，而且就在我们身边：
事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！
现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？
Input
输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=20），n表示8006的网友的人数。
Output
对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。
Sample Input
2
3
Sample Output
1
2
思路：
错排序列问题。难点在于找到递归式；初始状态F(1)=0,F(2)=1和状态转移式F(n)=(n-1)*F(n-2)
代码：
#include
int main()
{
__int64 n, i, a[21] = { 1, 2 };
for (i = 2; i
HDOJ1297:Children’s Queue——递推求解、大数运算
Problem Description
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (11、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F(n-1);
所以F(n)=F(n-1)+F(n-2)+F(n-4)。因为题目要求n取值在1000以内，超过了_int64的大小。所以要用大数运算来做。但是大数运算至今没搞懂，就直接从网上找了大数的模板了……
代码：
#include
#include
#include
using namespace std;
long long s[1010][1005];
int main()
{
int i,j,n;
memset(s,0,sizeof(s));
s[1][0]=1;s[2][0]=2;s[3][0]=4;s[4][0]=7;
for(i=5;i=10){
s[i][j+1]+=s[i][j]/10;
s[i][j]%=10;
}
}
}
while(cin>>n){
i=1000;
while(i--){
if(s[n][i]!=0)
break;
}
cout=0;i--)
printf("%d",s[n][i]);
cout
HDOJ2046：骨牌铺方格——递推问题
Problem Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
Input
输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。
Output
对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。
Sample Input
1
3
2
Sample Output
1
3
2
斐波那契数列解决，注意输出要用int64才行，否则WA。不要问我怎么知道的……
代码：
#include
#include
using namespace std;
int main()
{
_int64 fibn[51] = {1,2,3};
int i,j;
while (~scanf("%d", &i))
{
for (j = 3; j
HDOJ1274:展开字符串——字符串处理
Problem Description
在纺织CAD系统开发过程中，经常会遇到纱线排列的问题。
该问题的描述是这样的：常用纱线的品种一般不会超过25种，所以分别可以用小写字母表示不同的纱线，例如：abc表示三根纱线的排列；重复可以用数字和括号表示，例如：2(abc)表示abcabc；1(a)=1a表示a;2ab表示aab;如果括号前面没有表示重复的数字出现，则就可认为是1被省略了，如：cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑，也易于理解；但是计算机却不能理解。为了使计算机接受，就必须将简单紧凑的表达方式展开。某ACM队接受了此项任务。现在你就是该ACM队的一员，请你把这个程序编写完成。
已知条件：输入的简单紧凑表达方式的长度不超过250个字符；括号前表示重复的数不超过1000；不会出现除了数字、括号、小写字母以外的任何其他字符；不会出现括号不配对等错误的情况（错误处理已由ACM其他队员完成了）。
Input
本题有多个测试数据组，第一行输入的就是数据组数N，接着就是N行表达式，表达式是按照前面介绍的意义书写的。
Output
输出时含有N行，每行对应一个输入的表达式。
Sample Input
2
1(1a2b1(ab)1c)
3(ab2(4ab))
Sample Output
abbabc
abaaaabaaaababaaaabaaaababaaaabaaaab
栈问题。
代码：
#include
#include
#include
using namespace std;
string process(string s)
{
string ans;
stack x;
for(int i=0;i='0'&&s[i]='a'&&s[i]='0')
{
int num=x.top()-'0';
x.pop();
while(num--)
x.push(s[i]);
}
else
x.push(s[i]);
}
else if(s[i]==')')
{
string temp;
while(x.top()!='(')
{
temp.insert(temp.begin(),x.top());
x.pop();
}
x.pop();
int num;
if(x.empty()||!(x.top()>='0'&&x.top()>test;
while(test--)
{
cin>>s;
cout