一、实验一
1、数组分割
描述
已知由n(n≥2)个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。
输入
多组数据，每组数据两行。第一行为一个整数n，代表数组中有n个元素。第二行为数组中的n个元素（元素之间用空格分隔）。当n等于0时，输入结束。
输出
每组数据输出两行。第一行为子集A1，第二行为子集A2，每两个元素用空格分隔。
输入样例 1
4 1 2 3 4 5 9 8 1 1 1 0
输出样例 1
1 2 3 4 1 1 1 8 9
#include <iostream> #include <cstdlib> using namespace std; int k; void SetArray(int* data, int size) { for (int i = 0; i < size; i++) { cin >> data[i]; } } void Print(int* data, int size) { for (int i = 0; i < size; i++) { cout << data[i] << " "; } cout << endl; } void FindMax(int* data, int size) { int low = 0, high = size - 1; int low0 = 0, high0 = size - 1; k = size / 2; bool flag = true; while (flag) { int pivot = data[low]; while (low < high) { while (low < high && data[high] >= pivot) { high--; } if (low != high) { data[low] = data[high]; } while (low < high && data[low] <= pivot) { low++; } if (low != high) { data[high] = data[low]; } } data[low] = pivot; if (low == k - 1) flag = false; } else if (low < k - 1) { low0 = ++low; high = high0; } else { high0 = --high; low = low0; } } } int main() { int size, *data; while (cin >> size && size != 0) { data = new int[size]; SetArray(data, size); FindMax(data, size); int i; for (i = 0; i <k-1; i++) cout << data[i] << " "; cout << data[i] << endl; int j; for (j = k; j < size-1; j++) cout << data[j] << " "; cout << data[j] << endl; } return 0; }
2、
基于链表的两个一元多项式的基本运算
描述
给定两个一元多项式A(x)与B(x)，利用链表表示A(x)与B(x)，实现A(x)与B(x)的加法、减法、
乘法和求导运算。
输入
输入多组数据，总计n*( a+b+2)+1行。其中，第一行整数n代表总计有n组数据，之后依次输入 n组数据。每组数据包括a+b+2行，其中第一行是两个整数a和b，分别代表A(x)与B(x)的项数。 之后紧跟a行，每行两个整数a1和a2，分别代表A(x)每项的系数和指数，再之后紧跟b行，每行 两个整数b1和b2，分别代表B(x)每项的系数和指数，每组数据最后一行为一个字符（+、-、* 、'），分别代表多项式的加法、减法、乘法和求导运算。所有数据的绝对值小于100，指数大 于等于0。
输出
对于每组数据输出一行，按照多项式次数从大到小排列，参考格式：5x^17+22x^7+11x^1+7。
输入样例 1
4 1 1 1 0 1 1 + 4 3 7 0 3 1 9 8 5 17 8 1 22 7 -9 8 + 1 1 1 1 1 1 - 1 1 1 1 1 1 '
输出样例 1
1x^1+1 5x^17+22x^7+11x^1+7 0 1 1
#include<iostream> using namespace std; typedef struct LNode* List; struct LNode { int coef;//系数 int exp;//指数 List next; }; void InitList(List &L) { L = new LNode; L->next = NULL; } void CreatList(List &L,int a)//创建链表的时候从大到小创建 { List p,r; p = new LNode; L = new LNode; L->next = NULL; r = L; if (a == 0) { cin>>p->coef; cin>>p->exp; return; } for (int i = 0; i < a; i++) { int m, n; p = new LNode; cin >> m >> n; p->coef = m; p->exp = n; List q = L; while (q->next) { if (q->next->exp < p->exp) break; q = q->next; } p->next = q->next; q->next = p; } } List Add(List &La, List &Lb) { List pa, pb, pc; pa = La->next; pb = Lb->next; pc = La; while (pa&&pb) { if (pa->exp > pb->exp) { pc->next = pa; pa = pa->next; pc = pc->next; } else if (pa->exp < pb->exp) { pc->next = pb; pb = pb->next; pc = pc->next; } else { int sum = pa->coef + pb->coef; if (sum != 0) { pa->coef = sum; pc->next = pa; pc = pc->next; pa = pa->next; List q = pb; pb = pb->next; free(q); } else { List q = pa; pa = pa->next; free(q); q = pb; pb = pb->next; free(q); } } } pc->next = pa ? pa : pb; free(Lb); return La; } List Sub(List La, List Lb) { int sum; List pa, pb, pc; pa = La->next; pb = Lb->next; pc = La; while (pa&&pb) { if (pa->exp > pb->exp) { pc->next = pa; pa = pa->next; pc = pc->next; } else if (pa->exp < pb->exp) { pc->next = pb; pb = pb->next; pc = pc->next; } else { sum = pa->coef - pb->coef; if (sum) { pa->coef = sum; pc->next = pa; pc = pa; pa = pa->next; List q = pb; pb = pb->next; free(q); } else { List q = pa; pa = pa->next; free(q); q = pb; pb = pb->next; free(q); } } } if (pa) { pc->next = pa; } else { while (pb) { pb->coef = -1 * pb->coef; pc->next = pb; pc = pc->next; pb = pb->next; } pc->next = NULL; } free(Lb); return La; } void Print(List L) { List p; if (!L) { cout << "0" << endl; return; } p = L->next; int first = 1; while(p) { if (first) { first = 0; } else { if (p->coef > 0)//负数就有负号了 cout<<"+"; } if (p->exp == 0) cout << p->coef; else cout << p->coef << "x^" << p->exp; p = p->next; } if (first) cout << "0" << endl; else cout << endl; } List Mul(List &La,List &Lb) { List pa = La->next; List pb = Lb->next; if (!pa || !pb) { return NULL; } List Lc; InitList(Lc); List pc = new LNode; pc->coef = pa->coef*pb->coef; pc->exp = pa->exp + pb->exp; pc->next = NULL; Lc->next = pc; int n = 1; while (pa) { pb = Lb->next; while (pb) { List pnew =new LNode; pnew->coef= pa->coef*pb->coef; pnew->exp = pa->exp + pb->exp; pnew->next = NULL; List p = Lc; while (p->next) { if (pnew->exp == p->next->exp) { if (n == 1) break; else { p->next->coef += pnew->coef; n++; break; } } else if (pnew->exp < p->next->exp) { if (p->next->next == NULL) { p->next->next = pnew; n++; break; } else { p = p->next;//如果不是空的，就继续和下一个比较 } } else if (pnew->exp > p->next->exp) { pnew->next = p->next; p->next = pnew; n++; break; } } pb = pb->next; } pa = pa->next; } return Lc; } List Der(List &L) { List p = L; while (p->next) { if (p->next->exp == 0) { if (p->next->next == NULL) { p->next->exp = 0; p->next->coef = 0; return L; } List q = p->next; p->next = q->next; delete q; } else { p->next->coef *= p->next->exp; p->next->exp--; } p = p->next; } return L; }//求导 int main() { int n; cin >> n; char op; for (int i = 0; i < n; i++) { List La, Lb; int a, b; cin >> a >> b;//a是A（x）的项数 if(a==0) InitList(La); InitList(Lb); CreatList(La, a); CreatList(Lb, b); List c1, c2; cin >> op; switch (op) { case '+': { c1 = Add(La, Lb); Print(c1); break; } case '-': { c1 = Sub(La, Lb); Print(c1); break; } case'*': { c1 = Mul(La, Lb); Print(c1); break; } case'\'': { c1 = Der(La); Print(c1); c2 = Der(Lb); Print(c2); break; } } } return 0; }
二、实验二
1、
Ackermann函数的非递归求值
描述
已知Ackermann函数定义如下：
写出计算Ack(m,n)的非递归算法。
输入
多组数据，每组数据有一行，为两个整数m和n。当m和n都等于0时，输入结束。
输出
每组数据输出一行，为Ack(m,n)。
输入样例 1
2 1 0 0
输出样例 1
5
#include<iostream> using namespace std; int a[200][200]; int main() { int n, m; for (int i = 0; i <= 200; i++) { a[0][i] = i + 1; } for (int j = 1; j <= 200; j++)//m>0 { a[j][0] = a[j - 1][1]; for (int i = 1; i <= 200; i++) { a[j][i] = a[j - 1][a[j][i - 1]]; } } while (cin >> m >> n && (n != 0 || m != 0)) { cout << a[m][n] << endl; } return 0; }
2、
迷宫问题
描述
密密被困在一个迷宫里，迷宫有n个路口，编号为1-n。密密现在站在第一个路口，出口编号为m。先给出每个路口通向何处，问密密能否逃出迷宫。
输入
多组数据，每组数据n+2行。第一行为一个正整数n代表路口的个数，之后n行，这n行中的第i行为第i个路口的向左路口、向前路口、向右路口。最后一行为一个正整数m代表迷宫的终点。当n=0时输入结束。
输出
每组数据输出一行，若密密能走出迷宫，输出“YES”，否则输出“NO”。
输入样例 1
6 0 2 0 3 5 6 0 0 4 0 0 0 0 0 0 7 0 0 7 3 2 0 0 0 0 0 0 0 0 3 0
输出样例 1
YES NO
#include<iostream> #include<string> #include<cstring> using namespace std;//dfs int flag; int p[3]; int a[200][200]; void Dfs(int n,int m)//起点,终点 { if (n == m) { flag = 1; return; } for (int i = 0; i < 3; i++) { if (a[n][i] && !p[a[n][i]]) { p[a[n][i]] = 1; Dfs(a[n][i], m); p[a[n][i]] = 0;//??? } } } int main() { int n; int m; while (cin >> n && n != 0) { flag = 0; for (int i = 1; i <=n;i++) { for (int j = 0; j < 3; j++) { cin >> a[i][j]; } } cin >> m;//代表终点 p[1] = 1;//起点访问过 Dfs(1,m); if (flag == 1) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
3、
病毒感染监测
描述
医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的DNA序列都是环状的。现在研究者收集了大量的病毒DNA和人的DNA数据，想快速检测出这些人是否感染了相应的病毒。为方便研究，研究者将人的DNA和病毒的DNA均表示成由一些小写字母组成的字符串，然后检测某种病毒的DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了病毒，否则没有感染。注意：人的DNA序列是线性的，而病毒的DNA序列是环状的。
输入
多组数据，每组数据有一行，为序列A和B，A对应病毒的DNA序列，B对应人的DNA序列。A和B都为“0”时输入结束。
输出
对于每组数据输出一行，若患者感染了病毒输出“YES”，否则输出“NO”。
输入样例 1
abbab abbabaab baa cacdvcabacsd abc def 0 0
输出样例 1
YES YES NO
#include<iostream> #include<string> #include<cstring> using namespace std;//s的第一个字符和t比较，不相等就和第二个比较，如果一旦有不相等的就继续比较，设置一个标记，如果一直没有就更新一下s的顺序 void change(string &s,int &count) { int length; length = s.size(); char a = s[0]; for (int i = 1; i < length; i++) { s[i - 1] = s[i]; } s[length - 1] = a; count++; } bool Judge(string s, string t) { int flag=0; int count=0;//当count比s的长度大的时候，如果依然没找到就输出no； int length = s.size(); int ll = t.size(); while (1) { int i=0, j = 0; int tt = 0; while (j!=ll) { if (s[i] == t[j]) { i++; j++; if (i-1== 0) { tt = j-1; continue; } if (i-1== length - 1) { flag = 1; break; } } else if (s[i] != t[j]) { if (i == 0) { j++; continue; } else if (i != 0) { i = 0; j = tt + 1; continue; } } } if (flag == 1) break; else if (count < length) { change(s, count); } else break; } if (flag == 1) return true; else return false; } int main() { string s, t; while (cin >> s >> t && (s != "0" || t != "0")) { if (Judge(s, t)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }