信息管理网站开发的视频教程,一个女装店网站建设的策划模板,wordpress防盗链插件,农村网站平台建设方案文章目录 其他经典例题跳转链接41.基数排序法42.循序搜寻法#xff08;使用卫兵#xff09;43.二分搜寻法#xff08;搜寻原则的代表#xff09;44.插补搜寻法45.费氏搜寻法 其他经典例题跳转链接
C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠… 文章目录 其他经典例题跳转链接41.基数排序法42.循序搜寻法使用卫兵43.二分搜寻法搜寻原则的代表44.插补搜寻法45.费氏搜寻法 其他经典例题跳转链接
C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官一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) 魔方阵
41.基数排序法
说明在之前所介绍过的排序方法都是属于「比较性」的排序法也就是每次排序时 都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」radix sort则是属于「分配式排序」distribution sort基数排序法又称「桶子法」bucket sort或bin sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些「桶」中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O (nlog®m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的比较性排序法。 解法基数排序的方式可以采用LSDLeast sgnificant digital或MSDMost sgnificant digitalLSD的排序方式由键值的最右边开始而MSD则相反由键值的最左边开始。 以LSD为例假设原来有一串数值如下所示 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值在走访数值时将它们分配至编号0到9的桶子中
接下来将这些桶子中的数值重新串接起来成为以下的数列 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配这次是根据十位数来分配
接下来将这些桶子中的数值重新串接起来成为以下的数列 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕如果排序的对象有三位数以上则持续进行以上的动作直至最高位数为止。 LSD的基数排序适用于位数小的数列如果位数多的话使用MSD的效率会比较好MSD的方式恰与LSD相反是由高位数为基底开始进行分配其他的演 算方式则都相同。
#include stdio.h
#include stdlib.h int main(void) { int data[10] {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; int temp[10][10] {0}; int order[10] {0}; int i, j, k, n, lsd; k 0; n 1; printf(\n排序前: ); for(i 0; i 10; i) printf(%d , data[i]); putchar(\n); while(n 10) { for(i 0; i 10; i) { lsd ((data[i] / n) % 10); temp[lsd][order[lsd]] data[i]; order[lsd]; } printf(\n重新排列: ); for(i 0; i 10; i) { if(order[i] ! 0) for(j 0; j order[i]; j) { data[k] temp[i][j]; printf(%d , data[k]); k; } order[i] 0; } n * 10; k 0; } putchar(\n); printf(\n排序后: ); for(i 0; i 10; i) printf(%d , data[i]); return 0;
} 42.循序搜寻法使用卫兵
说明 搜寻的目的是在「已排序的资料」中寻找指定的资料而当中循序搜寻是最基本的搜寻法只要从资料开头寻找到最后看看是否找到资料即可。 解法 初学者看到循序搜寻多数都会使用以下的方式来进行搜寻
while(i MAX) { if(number[i] k) { printf(找到指定值); break; } i;
} 这个方法基本上没有错但是可以加以改善可以利用设定卫兵的方式省去if判断式卫兵通常设定在数列最后或是最前方假设设定在列前方好了索引0的 位置我们从数列后方向前找如果找到指定的资料时其索引值不是0表示在数列走访完之前就找到了在程式的撰写上只要使用一个while回圈就可 以了。
下面的程式为了配合卫兵的设置自行使用快速排序法先将产生的数列排序然后才进行搜寻若只是数字的话通常您可以使用程式语言函式库所提供的搜寻函式。
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 10
#define SWAP(x,y) {int t; t x; x y; y t;} int search(int[]);
int partition(int[], int, int);
void quicksort(int[], int, int); int main(void) { int number[MAX1] {0}; int i, find; srand(time(NULL)); for(i 1; i MAX; i) number[i] rand() % 100; quicksort(number, 1, MAX); printf(数列); for(i 1; i MAX; i) printf(%d , number[i]); printf(\n输入搜寻值); scanf(%d, number[0]); if(find search(number)) printf(\n找到数值于索引 %d , find); else printf(\n找不到数值); printf(\n); return 0;
} int search(int number[]) { int i, k; k number[0]; i MAX; while(number[i] ! k) i--; return i;
} int partition(int number[], int left, int right) { int i, j, s; s number[right]; i left - 1; for(j left; j right; j) { if(number[j] s) { i; SWAP(number[i], number[j]); } } SWAP(number[i1], number[right]); return i1;
} void quicksort(int number[], int left, int right) { int q; if(left right) { q partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q1, right); }
} 43.二分搜寻法搜寻原则的代表
说明如果搜寻的数列已经有排序应该尽量利用它们已排序的特性以减少搜寻比对的次数这是搜寻的基本原则二分搜寻法是这个基本原则的代表。 解法在二分搜寻法中从数列的中间开始搜寻如果这个数小于我们所搜寻的数由于数列已排序则该数左边的数一定都小于要搜寻的对象所以无需浪费时间在左边的数如果搜寻的数大于所搜寻的对象则右边的数无需再搜寻直接搜寻左边的数。
所以在二分搜寻法中将数列不断的分为两个部份每次从分割的部份中取中间数比对例如要搜寻92于以下的数列首先中间数索引为(09)/2 4索引由0开始 [3 24 57 57 67 68 83 90 92 95]
由于67小于92所以转搜寻右边的数列 3 24 57 57 67 [68 83 90 92 95] 由于90小于92再搜寻右边的数列这次就找到所要的数了 3 24 57 57 67 68 83 90 [92 95]
#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 quicksort(int[], int, int);
int bisearch(int[], int); int main(void) { int number[MAX] {0}; int i, find; srand(time(NULL)); for(i 0; i MAX; i) { number[i] rand() % 100; } quicksort(number, 0, MAX-1); printf(数列); for(i 0; i MAX; i) printf(%d , number[i]); printf(\n输入寻找对象); scanf(%d, find); if((i bisearch(number, find)) 0) printf(找到数字于索引 %d , i); else printf(\n找不到指定数); printf(\n); return 0;
} int bisearch(int number[], int find) { int low, mid, upper; low 0; upper MAX - 1; while(low upper) { mid (lowupper) / 2; if(number[mid] find) low mid1; else if(number[mid] find) upper mid - 1; else return mid; } return -1;
} void quicksort(int number[], int left, int right) { int i, j, k, s; if(left right) { s number[(leftright)/2]; i left - 1; j right 1; while(1) { while(number[i] s) ; // 向右找 while(number[--j] s) ; // 向左找 if(i j) break; SWAP(number[i], number[j]); } quicksort(number, left, i-1); // 对左边进行递回 quicksort(number, j1, right); // 对右边进行递回 }
} 44.插补搜寻法
说明 如果却搜寻的资料分布平均的话可以使用插补Interpolation搜寻法来进行搜寻在搜寻的对象大于500时插补搜寻法会比 二分搜寻法 来的快速。 解法 插补搜寻法是以资料分布的近似直线来作比例运算以求出中间的索引并进行资料比对如果取出的值小于要寻找的值则提高下界如果取出的值大于要寻找的 值则降低下界如此不断的减少搜寻的范围所以其本原则与二分搜寻法是相同的至于中间值的寻找是透过比例运算如下所示其中K是指定要寻找的对象 而m则是可能的索引值 #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 quicksort(int[], int, int);
int intsrch(int[], int); int main(void) { int number[MAX] {0}; int i, find; srand(time(NULL)); for(i 0; i MAX; i) { number[i] rand() % 100; } quicksort(number, 0, MAX-1); printf(数列); for(i 0; i MAX; i) printf(%d , number[i]); printf(\n输入寻找对象); scanf(%d, find); if((i intsrch(number, find)) 0) printf(找到数字于索引 %d , i); else printf(\n找不到指定数); printf(\n); return 0;
} int intsrch(int number[], int find) { int low, mid, upper; low 0; upper MAX - 1; while(low upper) { mid (upper-low)* (find-number[low])/(number[upper]-number[low]) low; if(mid low || mid upper) return -1; if(find number[mid]) upper mid - 1; else if(find number[mid]) low mid 1; else return mid; } return -1;
} void quicksort(int number[], int left, int right) { int i, j, k, s; if(left right) { s number[(leftright)/2]; i left - 1; j right 1; while(1) { while(number[i] s) ; // 向右找 while(number[--j] s) ; // 向左找 if(i j) break; SWAP(number[i], number[j]); } quicksort(number, left, i-1); // 对左边进行递回 quicksort(number, j1, right); // 对右边进行递回 }
} 45.费氏搜寻法
说明 二分搜寻法每次搜寻时都会将搜寻区间分为一半所以其搜寻时间为O(log(2)n)log(2)表示以2为底的log值这边要介绍的费氏搜寻其利用费氏数列作为间隔来搜寻下一个数所以区间收敛的速度更快搜寻时间为O(logn)。 解法 费氏搜寻使用费氏数列来决定下一个数的搜寻位置所以必须先制作费氏数列这在之前有提过费氏搜寻会先透过公式计算求出第一个要搜寻数的位置以及其代 表的费氏数以搜寻对象10个数字来说第一个费氏数经计算后一定是F5而第一个要搜寻的位置有两个可能例如若在下面的数列搜寻的话为了计算方便 通常会将索引0订作无限小的数而数列由索引1开始 -infin; 1 3 5 7 9 13 15 17 19 20 如果要搜寻5的话则由索引F5 5开始搜寻接下来如果数列中的数小于指定搜寻值时就往左找大于时就向右每次找的间隔是F4、F3、F2来寻找当费氏数为0时还没找到就表示寻找失败如下所示
由于第一个搜寻值索引F5 5处的值小于19所以此时必须对齐数列右方也就是将第一个搜寻值的索引改为F52 7然后如同上述的方式进行搜寻如下所示
至于第一个搜寻值是如何找到的我们可以由以下这个公式来求得其中n为搜寻对象的个数 Fx m n Fx n
也就是说Fx必须找到不大于n的费氏数以10个搜寻对象来说 Fx m 10
取Fx 8, m 2所以我们可以对照费氏数列得x 6然而第一个数的可能位置之一并不是F6而是第x-1的费氏数也就是F5 5。
如果数列number在索引5处的值小于指定的搜寻值则第一个搜寻位置就是索引5的位置如果大于指定的搜寻值则第一个搜寻位置必须加上m也就是F5 m 5 2 7也就是索引7的位置其实加上m的原因是为了要让下一个搜寻值刚好是数列的最后一个位置。
费氏搜寻看来难懂但只要掌握Fx m n这个公式自己找几个实例算一次很容易就可以理解费氏搜寻除了收敛快速之外由于其本身只会使用到加法与减法在运算上也可以加快。
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 15
#define SWAP(x,y) {int t; t x; x y; y t;} void createfib(void); // 建立费氏数列
int findx(int, int); // 找x值
int fibsearch(int[], int); // 费氏搜寻
void quicksort(int[], int, int); // 快速排序 int Fib[MAX] {-999}; int main(void) { int number[MAX] {0}; int i, find; srand(time(NULL)); for(i 1; i MAX; i) { number[i] rand() % 100; } quicksort(number, 1, MAX); printf(数列); for(i 1; i MAX; i) printf(%d , number[i]); printf(\n输入寻找对象); scanf(%d, find); if((i fibsearch(number, find)) 0) printf(找到数字于索引 %d , i); else printf(\n找不到指定数); printf(\n); return 0;
} // 建立费氏数列
void createfib(void) { int i; Fib[0] 0; Fib[1] 1; for(i 2; i MAX; i) Fib[i] Fib[i-1] Fib[i-2];
} // 找 x 值
int findx(int n, int find) { int i 0; while(Fib[i] n) i; i--; return i;
} // 费式搜寻
int fibsearch(int number[], int find) { int i, x, m; createfib(); x findx(MAX1,find); m MAX - Fib[x]; printf(\nx %d, m %d, Fib[x] %d\n\n, x, m, Fib[x]); x--; i x; if(number[i] find) i m; while(Fib[x] 0) { if(number[i] find) i Fib[--x]; else if(number[i] find) i - Fib[--x]; else return i; } return -1;
} void quicksort(int number[], int left, int right) { int i, j, k, s; if(left right) { s number[(leftright)/2]; i left - 1; j right 1; while(1) { while(number[i] s) ; // 向右找 while(number[--j] s) ; // 向左找 if(i j) break; SWAP(number[i], number[j]); } quicksort(number, left, i-1); // 对左边进行递回 quicksort(number, j1, right); // 对右边进行递回 }
} 系列好文点击链接即可跳转
C语言经典算法-7 排序法 - 改良的选择排序、快速排序法一、快速排序法二、快速排序法三、合并排序法
C语言经典算法-9 稀疏矩阵、多维矩阵转一维矩阵、上三角、下三角、对称矩阵、奇数魔方阵、4N 魔方阵、2(2N1) 魔方阵
