网站开发 如何备案,一小时学会网站建设,wordpress 图书插件,wordpress仿哔哩哔哩文章目录 其他经典例题跳转链接31.数字拆解32.得分排行33.选择、插入、气泡排序34.Shell 排序法 - 改良的插入排序35.Shaker 排序法 - 改良的气泡排序 其他经典例题跳转链接
C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官#xff08;一一6. 老鼠走迷官二7. 骑士走棋盘8. 八皇后9. 八枚银币10. 生命游戏
C语言经典算法-2 字串核对、双色、三色河内塔、背包问题Knapsack Problem、蒙地卡罗法求 PI、Eratosthenes筛选求质数
C语言经典算法-3 超长整数运算大数运算、长 PI、最大公因数、最小公倍数、因式分解、完美数、阿姆斯壮数
C语言经典算法-4 最大访客数、中序式转后序式前序式、后序式的运算、洗扑克牌乱数排列、Craps赌博游戏
C语言经典算法-5 约瑟夫问题Josephus Problem、排列组合、格雷码Gray Code)、产生可能的集合、m元素集合的n个元素子集
C语言经典算法-6 数字拆解、得分排行选择、插入、气泡排序、Shell 排序法 - 改良的插入排序、Shaker 排序法 - 改良的气泡排序
C语言经典算法-7 排序法 - 改良的选择排序、快速排序法一、快速排序法二、快速排序法三、合并排序法
C语言经典算法-8 基数排序法、循序搜寻法使用卫兵、二分搜寻法搜寻原则的代表、插补搜寻法、费氏搜寻法
C语言经典算法-9 稀疏矩阵、多维矩阵转一维矩阵、上三角、下三角、对称矩阵、奇数魔方阵、4N 魔方阵、2(2N1) 魔方阵
31.数字拆解
说明 这个题目来自于 数字拆解我将之改为C语言的版本并加上说明。
题目是这样的 3 21 111 所以3有三种拆法 4 3 1 2 2 2 1 1 1 1 1 1 共五种 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
共七种
依此类推请问一个指定数字NUM的拆解方法个数有多少个 解法 我们以上例中最后一个数字5的拆解为例假设f( n )为数字n的可拆解方式个数而f(x, y)为使用y以下的数字来拆解x的方法个数则观察 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
使用函式来表示的话 f(5) f(4, 1) f(3,2) f(2,3) f(1,4) f(0,5)
其中f(1, 4) f(1, 3) f(1, 2) f(1, 1)但是使用大于1的数字来拆解1没有意义所以f(1, 4) f(1, 1)而同样的f(0, 5)会等于f(0, 0)所以 f(5) f(4, 1) f(3,2) f(2,3) f(1,1) f(0,0)
依照以上的说明使用动态程式规画Dynamic programming来进行求解其中f(4,1)其实就是f(5-1, min(5-1,1))f(x, y)就等于f(n-y, min(n-x, y))其中n为要拆解的数字而min()表示取两者中较小的数。
使用一个二维阵列表格table[x][y]来表示f(x, y)刚开始时将每列的索引0与索引1元素值设定为1因为任何数以0以下的数拆解必只有1种而任何数以1以下的数拆解也必只有1种
for(i 0; i NUM 1; i){ table[i][0] 1; // 任何数以0以下的数拆解必只有1种 table[i][1] 1; // 任何数以1以下的数拆解必只有1种
}接下来就开始一个一个进行拆解了如果数字为NUM则我们的阵列维度大小必须为NUM x (NUM/21)以数字10为例其维度为10 x 6我们的表格将会如下所示 1 1 0 0 0 0 1 1 0 0 0 0 1 1 2 0 0 0 1 1 2 3 0 0 1 1 3 4 5 0 1 1 3 5 6 7 1 1 4 7 9 0 1 1 4 8 0 0 1 1 5 0 0 0 1 1 0 0 0 0
实作
C
#include stdio.h
#include stdlib.h
#define NUM 10 // 要拆解的数字
#define DEBUG 0 int main(void) { int table[NUM][NUM/21] {0}; // 动态规画表格 int count 0; int result 0; int i, j, k; printf(数字拆解\n); printf(3 21 111 所以3有三种拆法\n); printf(4 3 1 2 2 2 1 1 1 1 1 1); printf(共五种\n); printf(5 4 1 3 2 3 1 1);printf( 2 2 1 2 1 1 1 1 1 1 1 1);printf(共七种\n); printf(依此类推求 %d 有几种拆法, NUM); // 初始化 for(i 0; i NUM; i){ table[i][0] 1; // 任何数以0以下的数拆解必只有1种 table[i][1] 1; // 任何数以1以下的数拆解必只有1种 } // 动态规划 for(i 2; i NUM; i){ for(j 2; j i; j){ if(i j NUM) // 大于 NUM continue; count 0; for(k 1 ; k j; k){ count table[i-k][(i-k k) ? k : i-k]; } table[i][j] count; } } // 计算并显示结果 for(k 1 ; k NUM; k) result table[NUM-k][(NUM-k k) ? k : NUM-k]; printf(\n\nresult: %d\n, result); if(DEBUG) { printf(\n除错资讯\n); for(i 0; i NUM; i) { for(j 0; j NUM/21; j) printf(%2d, table[i][j]); printf(\n); } } return 0;
} 32.得分排行
说明假设有一教师依学生座号输入考试分数现希望在输入完毕后自动显示学生分数的排行当然学生的分数可能相同。 解法这个问题基本上要解不难只要使用额外的一个排行阵列走访分数阵列就可以了直接使用下面的程式片段作说明
for(i 0; i count; i) { juni[i] 1; for(j 0; j count; j) { if(score[j] score[i]) juni[i]; }
}
printf(得分\t排行\n);
for(i 0; i count; i) printf(%d\t%d\n, score[i], juni[i]); 上面这个方法虽然简单但是反覆计算的次数是n^2如果n值变大那么运算的时间就会拖长改变juni阵列的长度为n2并将初始值设定为0如下所示
接下来走访分数阵列并在分数所对应的排行阵列索引元素上加1如下所示
将排行阵列最右边的元素设定为1然后依序将右边的元素值加至左边一个元素最后排行阵列中的「分数1」」就是得该分数的排行如下所示
这样的方式看起来复杂其实不过在计算某分数之前排行的人数假设89分之前的排行人数为x人则89分自然就是x1了这也是为什么排行阵列最右边要设定为1的原因如果89分有y人则88分自然就是xy1整个阵列右边元素向左加的原因正是如此。 如果分数有负分的情况由于C/C或Java等程式语言无法处理负的索引所以必须加上一个偏移值将所有的分数先往右偏移一个范围即可最后显示的时候记得减回偏移值就可以了。
#include stdio.h
#include stdlib.h
#define MAX 100
#define MIN 0 int main(void) { int score[MAX1] {0}; int juni[MAX2] {0}; int count 0, i; do { printf(输入分数-1结束); scanf(%d, score[count]); } while(score[count-1] ! -1);count--; for(i 0; i count; i) juni[score[i]]; juni[MAX1] 1; for(i MAX; i MIN; i--) juni[i] juni[i] juni[i1]; printf(得分\t排行\n); for(i 0; i count; i) printf(%d\t%d\n, score[i], juni[score[i]1]); return 0;
} 33.选择、插入、气泡排序
说明选择排序Selection sort、插入排序Insertion sort与气泡排序Bubble sort这三个排序方式是初学排序所必须知道的三个基本排序方式它们由于速度不快而不实用平均与最快的时间复杂度都是O(n2)然而它们排序的方式确是值得观察与探讨的。 解法 选择排序 将要排序的对象分作两部份一个是已排序的一个是未排序的从后端未排序部份选择一个最小值并放入前端已排序部份的最后一个例如
排序前70 80 31 37 10 1 48 60 33 80
[1] 80 31 37 10 70 48 60 33 80 选出最小值1 [1 10] 31 37 80 70 48 60 33 80 选出最小值10 [1 10 31] 37 80 70 48 60 33 80 选出最小值31 [1 10 31 33] 80 70 48 60 37 80 … [1 10 31 33 37] 70 48 60 80 80 … [1 10 31 33 37 48] 70 60 80 80 … [1 10 31 33 37 48 60] 70 80 80 … [1 10 31 33 37 48 60 70] 80 80 … [1 10 31 33 37 48 60 70 80] 80 …
插入排序 像是玩朴克一样我们将牌分作两堆每次从后面一堆的牌抽出最前端的牌然后插入前面一堆牌的适当位置例如
排序前92 77 67 8 6 84 55 85 43 67
[77 92] 67 8 6 84 55 85 43 67 将77插入92前 [67 77 92] 8 6 84 55 85 43 67 将67插入77前 [8 67 77 92] 6 84 55 85 43 67 将8插入67前 [6 8 67 77 92] 84 55 85 43 67 将6插入8前 [6 8 67 77 84 92] 55 85 43 67 将84插入92前 [6 8 55 67 77 84 92] 85 43 67 将55插入67前 [6 8 55 67 77 84 85 92] 43 67 … [6 8 43 55 67 77 84 85 92] 67 … [6 8 43 55 67 67 77 84 85 92] …
气泡排序法 顾名思义就是排序时最大的元素会如同气泡一样移至右端其利用比较相邻元素的方法将大的元素交换至右端所以大的元素会不断的往右移动直到适当的位置为止。
基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间当寻访完阵列后都没有发生任何的交换动作表示排序已经完成而无需再进行之后的回圈比较与交换动作例如
排序前95 27 90 49 80 58 6 9 18 50
27 90 49 80 58 6 9 18 50 [95] 95浮出 27 49 80 58 6 9 18 50 [90 95] 90浮出 27 49 58 6 9 18 50 [80 90 95] 80浮出 27 49 6 9 18 50 [58 80 90 95] … 27 6 9 18 49 [50 58 80 90 95] … 6 9 18 27 [49 50 58 80 90 95] … 6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作排序提早结束
在上面的例子当中还加入了一个观念就是当进行至i与i1时没有交换的动作表示接下来的i2至n已经排序完毕这也增进了气泡排序的效率。
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 10
#define SWAP(x,y) {int t; t x; x y; y t;} void selsort(int[]); // 选择排序
void insort(int[]); // 插入排序
void bubsort(int[]); // 气泡排序 int main(void) { int number[MAX] {0}; int i; srand(time(NULL)); printf(排序前); for(i 0; i MAX; i) { number[i] rand() % 100; printf(%d , number[i]); } printf(\n请选择排序方式\n); printf((1)选择排序\n(2)插入排序\n(3)气泡排序\n:); scanf(%d, i); switch(i) { case 1: selsort(number); break; case 2: insort(number); break; case 3: bubsort(number); break; default: printf(选项错误(1..3)\n); } return 0;
} void selsort(int number[]) { int i, j, k, m; for(i 0; i MAX-1; i) { m i; for(j i1; j MAX; j) if(number[j] number[m]) m j; if( i ! m) SWAP(number[i], number[m]) printf(第 %d 次排序, i1); for(k 0; k MAX; k) printf(%d , number[k]); printf(\n); } } void insort(int number[]) { int i, j, k, tmp; for(j 1; j MAX; j) { tmp number[j]; i j - 1; while(tmp number[i]) { number[i1] number[i]; i--; if(i -1) break; } number[i1] tmp; printf(第 %d 次排序, j); for(k 0; k MAX; k) printf(%d , number[k]); printf(\n); }
} void bubsort(int number[]) { int i, j, k, flag 1; for(i 0; i MAX-1 flag 1; i) { flag 0; for(j 0; j MAX-i-1; j) { if(number[j1] number[j]) { SWAP(number[j1], number[j]); flag 1; } } printf(第 %d 次排序, i1); for(k 0; k MAX; k) printf(%d , number[k]); printf(\n); }
} 34.Shell 排序法 - 改良的插入排序
说明 插入排序法由未排序的后半部前端取出一个值插入已排序前半部的适当位置概念简单但速度不快。
排序要加快的基本原则之一是让后一次的排序进行时尽量利用前一次排序后的结果以加快排序的速度Shell排序法即是基于此一概念来改良插入排序法。 解法 Shell排序法最初是D.L Shell于1959所提出假设要排序的元素有n个则每次进行插入排序时并不是所有的元素同时进行时而是取一段间隔。
Shell首先将间隔设定为n/2然后跳跃进行插入排序再来将间隔n/4跳跃进行排序动作再来间隔设定为n/8、n/16直到间隔为1之后的最 后一次排序终止由于上一次的排序动作都会将固定间隔内的元素排序好所以当间隔越来越小时某些元素位于正确位置的机率越高因此最后几次的排序动作将 可以大幅减低。
举个例子来说假设有一未排序的数字如右89 12 65 97 61 81 27 2 61 98
数字的总数共有10个所以第一次我们将间隔设定为10 / 2 5此时我们对间隔为5的数字进行排序如下所示
画线连结的部份表示 要一起进行排序的部份再来将间隔设定为5 / 2的商也就是2则第二次的插入排序对象如下所示
再来间隔设定为2 / 2 1此时就是单纯的插入排序了由于大部份的元素都已大致排序过了所以最后一次的插入排序几乎没作什么排序动作了 将间隔设定为n / 2是D.L Shell最初所提出在教科书中使用这个间隔比较好说明然而Shell排序法的关键在于间隔的选定例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度
其中4*(2j)2 3*(2j) 1不可超过元素总数n值使用上式找出j后代入4*(2j)2 3*(2j) 1求得第一个间隔然后将2j除以2代入求得第二个间隔再来依此类推。
后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快另外Shell排序法的概念也可以用来改良气泡排序法。 实作
C
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 10
#define SWAP(x,y) {int t; t x; x y; y t;} void shellsort(int[]); int main(void) { int number[MAX] {0}; int i; srand(time(NULL)); printf(排序前); for(i 0; i MAX; i) { number[i] rand() % 100; printf(%d , number[i]); } shellsort(number); return 0;
} void shellsort(int number[]) { int i, j, k, gap, t; gap MAX / 2; while(gap 0) { for(k 0; k gap; k) { for(i kgap; i MAX; igap) { for(j i - gap; j k; j-gap) { if(number[j] number[jgap]) { SWAP(number[j], number[jgap]); } else break; } } } printf(\ngap %d, gap); for(i 0; i MAX; i) printf(%d , number[i]); printf(\n); gap / 2; }
} 35.Shaker 排序法 - 改良的气泡排序
说明 请看看之前介绍过的气泡排序法 for(i 0; i MAX-1 flag 1; i) { flag 0; for(j 0; j MAX-i-1; j) { if(number[j1] number[j]) { SWAP(number[j1], number[j]); flag 1; } }
} 事实上这个气泡排序法已经不是单纯的气泡排序了它使用了旗标与右端左移两个方法来改进排序的效能而Shaker排序法使用到后面这个观念进一步改良气泡排序法。 解法 在上面的气泡排序法中交换的动作并不会一直进行至阵列的最后一个而是会进行至MAX-i-1所以排序的过程中阵列右方排序好的元素会一直增加使得左边排序的次数逐渐减少如我们的例子所示
排序前95 27 90 49 80 58 6 9 18 50
27 90 49 80 58 6 9 18 50 [95] 95浮出 27 49 80 58 6 9 18 50 [90 95] 90浮出 27 49 58 6 9 18 50 [80 90 95] 80浮出 27 49 6 9 18 50 [58 80 90 95] … 27 6 9 18 49 [50 58 80 90 95] … 6 9 18 27 [49 50 58 80 90 95] … 6 9 18 [27 49 50 58 80 90 95]
方括号括住的部份表示已排序完毕Shaker排序使用了这个概念如果让左边的元素也具有这样的性质让左右两边的元素都能先排序完成如此未排序的元素会集中在中间由于左右两边同时排序中间未排序的部份将会很快的减少。
方法就在于气泡排序的双向进行先让气泡排序由左向右进行再来让气泡排序由右往左进行如此完成一次排序的动作而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。
一个排序的例子如下所示
排序前45 19 77 81 13 28 18 19 77 11
往右排序19 45 77 13 28 18 19 77 11 [81] 向左排序[11] 19 45 77 13 28 18 19 77 [81]
往右排序[11] 19 45 13 28 18 19 [77 77 81] 向左排序[11 13] 19 45 18 28 19 [77 77 81]
往右排序[11 13] 19 18 28 19 [45 77 77 81] 向左排序[11 13 18] 19 19 28 [45 77 77 81]
往右排序[11 13 18] 19 19 [28 45 77 77 81] 向左排序[11 13 18 19 19] [28 45 77 77 81]
如上所示括号中表示左右两边已排序完成的部份当left right时则排序完成。
实作
C
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 10
#define SWAP(x,y) {int t; t x; x y; y t;} void shakersort(int[]); int main(void) { int number[MAX] {0}; int i; srand(time(NULL)); 系列好文点击链接即可跳转
C语言经典算法-5 约瑟夫问题Josephus Problem、排列组合、格雷码Gray Code)、产生可能的集合、m元素集合的n个元素子集
C语言经典算法-7 排序法 - 改良的选择排序、快速排序法一、快速排序法二、快速排序法三、合并排序法
