the sum of two fixed value description Input an array and an integer, fina a pair of number in the array so that the sum is equals to the inputed integer. If there are several pairs, you can output any pair. For example, if the input array is [1,2,4,5,7,11,15] and an integer 15, because 4 + 11 = 15, hence output 4 and 11. analysis and solution We try to figure out this problem step by step. (we should notice the difference of ordered and unordered.)

数据结构线性表是数据结构最基础的一章内容，也是数据结构最基础的一段，包括线性表的定义，线性表的初始化，线性表的插入，删除，合并。下面贴上代码 #include <stdio.h> #include <malloc.h> #include<iostream> using namespace std; //线性表的定义 typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; //线性表的初始化 int InitList_L(LinkList &L) { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; return 1; } //线性表的插入 int ListInsert_L(LinkList &L,int i,ElemType e) { LinkList p; p = L; int j = 0; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) return 0; LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = e; s->next=p->next; p->next=s; return 1; } //清空线性表 void Delete_L(LinkList L) { LinkList p = L->next; if(!p) cout << "this list is empty!"; while(p) { cout << p->data; p = p->next; } cout << endl; } //合并线性表 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { LinkList pa = La->next; LinkList pb = Lb->next; LinkList pc = Lc=La; while (pa&&pb) { if(pa->data<pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); } int main() { LinkList La,Lb,Lc; InitList_L(La); InitList_L(Lb); InitList_L(Lc); ListInsert_L(La,1,2); ListInsert_L(La,2,3); ListInsert_L(La,3,5); Delete_L(La); }

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都是按照从上到下递增的顺序排序。请设计一个函数，输入这样的一个二维数组和一个整数，判断数组是否含有这个整数。 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 我们可以发现以下规律：首先选取数组右上角的数字。如果这个数字是要寻找的数字，则返回结果。若这个数字大于我们要寻找的数字，则去除这个数字所在的列；若这个数字小于我们要寻找的数字，则去除这个数字所在的行。也就是说如果查找的数字不在数组的右上角，则每一次都在数组查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围了，直到找到需要查找的数字或者查找的范围为空。 从另外一个角度看，从左下角的数字来看，如果这个数字大于查找的数字，则剔除该行，若这个数字小于查找的数字，则剔除该列。 bool Find(int* matrix,int rows,int cols,int num) { bool found = false; if (matrix != null && rows > 0 && cols > 0) { int row = 0; int col = cols - 1; while(row < rows && col >= 0) { if (matrix[row*cols + col] == num) { found = true; break; } else if(matrix[row*cols + col] > num) -- col; else ++ row; } } return found; }

现在找工作的压力这么大，为了以后好找工作，现在开始要多看看算法，所以以后可以每天做个小题目，练习一下。今天作为第一天，说个最简单的直接插入排序。 直接插入排序可以这么理解，把A[j]和A[0]….A[j-1]的数进行比较，如果比他们小，就插入到比它小的前一位，直接插入排序的时间复杂度是O(n^2). 先给出伪代码分析 //the index of array is from 0 for j=1 to num.length key = num[j]; i = j-1; while i >= 0 and num[i] > key { num[i+1] = num[i]; i--; } num[i+1] = key; 下面用c++来实现 // insertsort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<iostream> #include<stdlib.h> using namespace std; int main() { int num[10] = {10,20,1,78,34,99,12,21,2,55}; int key; cout << "the number has not been sorted:" << endl; for (int i = 0;i < 10;i++) { cout << num[i] << ' '; } cout << endl; cout << "the number has been sorted:" << endl; for (int j =1;j <10;j++) { int key = num[j]; int i = j-1; while(i >=0&&num[i]>key) { num[i+1] = num[i]; i--; } num[i+1] = key; } for (int m = 0;m < 10;m++) { cout << num[m] << ' '; } cout << endl; return 0; } 今天一练，到此结束。

题目 Description 歌德巴赫猜想，是指对于每一个大于4的偶数ｎ，都能表示成两个质数之和。 现在，你需要写程序验证这一猜想。对于n，找出质数a和b, 满足a+b=n, a≤b，且a*b最大。例如n=8，满足条件的a和b分别为3和5； 又如n=10，质数3、7以及5、5满足a+b=n, a≤b，而乘积大的那组是5、5。 Input 每行一个偶数n（4 < n <= 20000） Output 对应于每个输入的偶数，输出a、一个空格、b、一个换行符 Sample Input 8 10 1000 Sample Output 3 5 5 5 491 509 代码 #include<stdio.h> #include<math.h> bool isPrime(int x); int main() { int n,i,j; while (scanf("%d",&n) != EOF) { for (i = n/2;i > 0;i -= 2) { if(i%2 == 0) i --; j = n - i; if(isPrime(i)&&isPrime(j)) { printf("%d %d\n",i,j); break; } } } return 0; } bool isPrime(int x) { int len = sqrt((float)x); for (int i = 2;i <= len;i ++) { if(x % i == 0) return false; } return true; }

问题 ROT13（回转13位）是一种简易的替换式密码算法。它是一种在英文网络论坛用作隐藏八卦、妙句、谜题解答以及某些脏话的工具，目的是逃过版主或管理员的匆匆一瞥。ROT13 也是过去在古罗马开发的凯撒密码的一种变体。ROT13是它自身的逆反，即：要还原成原文只要使用同一算法即可得，故同样的操作可用于加密与解密。该算法并没有提供真正密码学上的保全，故它不应该被用于需要保全的用途上。它常常被当作弱加密示例的典型。 应用ROT13到一段文字上仅仅只需要检查字母顺序并取代它在13位之后的对应字母，有需要超过时则重新绕回26英文字母开头即可。A换成N、B换成O、依此类推到M换成Z，然后串行反转：N换成A、O换成B、最后Z换成M（如图所示）。只有这些出现在英文字母里的字符受影响；数字、符号、空白字符以及所有其他字符都不变。替换后的字母大小写保持不变。 例如，下面的英文笑话，精华句被ROT13所隐匿： How can you tell an extrovert from an introvert at NSA? Va gur ryringbef, gur rkgebireg ybbxf ng gur BGURE thl’f fubrf. 通过ROT13转换，该笑话的解答揭露如下： Ubj pna lbh gryy na rkgebireg sebz na vagebireg ng AFN? In the elevators, the extrovert looks at the OTHER guy’s shoes. 第二次使用ROT13将恢复为原文。 Input 第1行：一个整数T（1≤T≤10）为问题数。 接下来共T行。每行为长度不超过1000个字符的一段文字。内含大小写字母、空格、数字和各种符号等。 Output 对于每个问题，输出一行问题的编号（0开始编号，格式：case #0: 等）。 然后对应每个问题在一行中输出经过ROT13加密后的一段文字。 Sample Input 3 How can you tell an extrovert from an introvert at NSA? Va gur ryringbef,

有一天同学给了一个非常简单的算题，我居然写了半天，这次我要把它记录下来，以此明志，以后应该要更加注重这方面的锻炼。 题目 ime Limit: 1000 MS Memory Limit: 32768 K 给定两个同样长度的整数数组a[n]和b[n]，按照公式c[n]=a[n] * 2 - b[n]生成数组c[n]，并输出。 输入格式： 共2行数据，每一行是以空格为分隔符的数组，第一个数是一个正整数n，表示数组元素的个数（2<=n<=100)， 接下来是n个正整数表示数组元素,每个整数不超过100。 输出格式： 共1行数据，第一行是以空格为分隔符的数组，第一个数是一个正整数n，表示数组元素的个数（2<=n<=100)，接下来是n个正整数表示数组元素,每个整数不超过100。 样例： 输入： 10 18 38 83 93 53 36 39 58 8 93 10 55 79 20 71 60 66 79 55 78 66 输出 10 -19 -3 146 115 46 6 -1 61 -62 120 代码 #include "stdafx.h" #include<iostream> using namespace std; int main() { int a[100],b[100],c[100]; int n,n_; cin >> n; int m,m_; for (int i = 0; i < n;++ i) { cin >> m; a[i] = m; } cin >>n_; for (int i = 0;i < n; ++ i) { cin >> m_; b[i] = m_; } for (int i = 0;i <= n;i++) { if (i == 0) cout << n << " "; else cout << a[i-1]*2 - b[i-1] << " "; } return 0; } 这个程序很简单，只是数组的输入输出就好了，以后应该还是要找点OJ题目练习一下。