C++基础算法

一、 数学问题：

1、 素数判断

a、 判断一个数是不是素数

b、 利用筛选法，求出2----1000000中素数的个数。

2、 最大公约数 3、 最小公倍数 4、 素因数分解

二、 数据处理：

1、 数据查找：顺序查找、二分（折半）查找, 查找第k小元素。

2、甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆可带一人的小车。 又甲、乙两人步行速度相同。问，怎样利用小车才能使两人尽快同时到达。 输入：S=120 (AB两地之间的距离) a = 5 （步行速度） b = 25 (汽车速度) 输出：T= 9.60

输入：S=200 (AB两地之间的距离) a = 30 （步行速度） b = 50 (汽车速度) 输出：T= 5.143

3、 数据插入：顺序插入、二分插入

4、 排序：冒泡排序、选择排序、插入排序、快速排序

归并排序（提高组）、堆排序（提高组）、希尔排序（提高组）

5、数据合并：两个有序数组归并为一个有序数组（相同数据只取一个）

6、多项式。输入两个多项式的系数和指数，求两个多项式的和。

7、矩阵：

a、 矩阵相乘

b、 稀疏矩阵的存储，相乘

三、高精度运算

1、任意进制转换 2、高精度四则运算

加、减、乘（高精*单精，高精*高精）、除法（高精/高精，高精/单精）

四、字符串

1、 子串：求一个字符串的所有子串 2、回文数的判断

3、 统计文章中单词的数目

五、数据模拟

1、约瑟夫问题 （用静态指针模拟）

有编号为1，2…n的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码开始给定一个正整数m，从第一人按顺时针方向自1开始顺序报数，报到m者出围坐的圈子，不在参加报数，这时将出列者的密码作为m，出列者顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人都出围坐。请编写程序输出出列的顺序。 e.g：

1 2 3 4 5 {围坐者的序号} 8 7 3 6 5{围坐者的密码} 初始态：m=18

当报数到序号为3的人时，应该出列，结果：

1 2 4 5 {围坐者的序号} 8 7 6 5{密码}

此时m=3，从4号开始报数…… 答案：出列的顺序：3 1 4 2 5

2、奇数幻方

设有 n*n 方格的棋盘（n为奇数），将1，2，…..n*n个数填入到棋盘中，使所有的行、

列、对角线的和都相等。 例如： N=3

4 9 2 3 5 7 8 1 6 采用对角线走向的算法

步骤1： 1 的位置是(n div 2 +1, n )

步骤2：若a[i,j] = k ，k+1的位置在k的右下角，如果右下角已经有数据，则放在k同一行的前一个位置；如果行溢出，则将其行号改为1；如果列溢出，则将其列号改为1;如果行列同时溢出，则放在k同一行的前一个位置。

六、排列组合问题

1、全排列非递归算法。1…N的全排列。（元素不重复） 组合的非递归算法。

2、1..n中选m个元素的递归算法。（元素不重复） 输入:m,n 输出：总个数、各种组合（排列）

3、n个元素中最多、最少取m个的排列、组合

4、全组合算法。

砝码称重：设有1g，2g,，5g,，10g，20g，50g的砝码个数分别为3 ，4，5，0，2，7，问用这些砝码可称出多少种不同的重量。

5、n个元素中取m个的排列、组合（n个元素可重复，元素重复个数不定）。

例如：A ，B中取3个元素的全排列和组合。 排列（AAA,AAB,ABA,BAA,ABB,BAB,BBA,BBB） 组合（AAA,AAB,ABB,BBB）

6、 无重复元素的环状的排列问题

七、递归与回溯算法

1、 2、 3、 4、 5、

13皇后问题

0-1背包问题（要求有分枝限界） 数字的拆分问题 旅行商问题 赛程安排问题.

有n（n=2^m)编号为1 到n的运动队,参加某项运动的单循环比赛,请安排一个比赛日程?（共n-1天比赛,每天每队必须比赛一场）。

八、表达式的处理。

（表达式中包括”+”、”-“、”*”、”/”，”(”，”)”） 1、 一个代数表达式的合法性判断 2、 一个代数表达式的求值 3、 删除表达式中多余的括号

九、树

1、输入一棵树的节点数、父节点，求一棵树的度和深度 ** 2、哈夫曼编码的生成算法。**

十、图论

1、深度优先搜索和广度优先搜索算法（用来求图的连通分支数，图的遍历）

A、倒水问题 B、细胞问题

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有4个细胞。 2、图的一笔画问题

3、图的最短路径问题（Dijkstra） ** 4、图的最小生成树（MST） **

5、图的拓扑排序及其应用 ** 6、图的关键路径算法 **

十一、动态规划

1、 最长公共子序列 2、 最长不降子序列 3、 石子合并问题

**

（以上带**初中不要求）

十二、递归和分治 题1：组合数comb.pas

时间限制：1s 输入文件：comb.in 输出文件：comb.out

在n 个数据（1-n的整数）中选m个数据进行组合。

在输入文件的第一行是n 和m, (n,m<6), 输出各对组合到文件中，每对组合占一行，最后一行是组合的总数。 例如： 输入：4 2 输出：1 2 1 3 1 4 2 3 2 4 3 4 6

题2 数的计算(20分) (count.pas ,count.in ,count.out)

问题描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理: 1. 不作任何处理;

2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.

样例: 输入: 6

满足条件的数为 6 (此部分不必输出) 16 26 126 36