C语言经典算法-8

文章目录

  • 其他经典例题跳转链接
    • 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(2N+1) 魔方阵

41.基数排序法

说明在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶」中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。
解法基数排序的方式可以采用LSD(Least sgnificant digital)或MSD(Most sgnificant digital),LSD的排序方式由键值的最右边开始,而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[MAX+1] = {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[i+1], number[right]); return i+1; 
} 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, q+1, right); } 
} 

43.二分搜寻法(搜寻原则的代表)

说明如果搜寻的数列已经有排序,应该尽量利用它们已排序的特性,以减少搜寻比对的次数,这是搜寻的基本原则,二分搜寻法是这个基本原则的代表。
解法在二分搜寻法中,从数列的中间开始搜寻,如果这个数小于我们所搜寻的数,由于数列已排序,则该数左边的数一定都小于要搜寻的对象,所以无需浪费时间在左边的数;如果搜寻的数大于所搜寻的对象,则右边的数无需再搜寻,直接搜寻左边的数。

所以在二分搜寻法中,将数列不断的分为两个部份,每次从分割的部份中取中间数比对,例如要搜寻92于以下的数列,首先中间数索引为(0+9)/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 = (low+upper) / 2; if(number[mid] < find) low = mid+1; 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[(left+right)/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, j+1, 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[(left+right)/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, j+1, 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,所以此时必须对齐数列右方,也就是将第一个搜寻值的索引改为F5+2 = 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(MAX+1,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[(left+right)/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, j+1, right);  // 对右边进行递回 } 
} 

系列好文,点击链接即可跳转

C语言经典算法-7
排序法 - 改良的选择排序、快速排序法(一)、快速排序法(二)、快速排序法(三)、合并排序法

C语言经典算法-9
稀疏矩阵、多维矩阵转一维矩阵、上三角、下三角、对称矩阵、奇数魔方阵、4N 魔方阵、2(2N+1) 魔方阵

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284963.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【每周赠书活动第1期】Python编程 从入门到实践 第3版(图灵出品)

编辑推荐 适读人群 &#xff1a;本书适合对Python感兴趣的所有读者阅读。 编程入门就选蟒蛇书&#xff01; 【经典】Python入门经典&#xff0c;常居Amazon等编程类图书TOP榜 【畅销】热销全球&#xff0c;以12个语种发行&#xff0c;影响超过 250 万读者 【口碑】好评如潮…

Python文件读写操作

文件操作注意点 注意点&#xff1a; 1. for line in file --> 会将偏移量移到末尾 2. buffering1 --> 缓冲区中遇到换行就刷新&#xff0c;即向磁盘中写入 3. 读操作结束后&#xff0c;文本偏移量就会移动到读操作结束位置 """编写一个程序,循环不停的写入…

有哪些强大好用的AI表格数据处理工具或者 AI Excel工具?

在繁忙的工作和生活中&#xff0c;处理大量的表格数据往往令人感到头疼。面对一列列数字、一行行文字&#xff0c;我们需要花费大量的时间和精力去整理、核对。然而&#xff0c;随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;技术正逐渐改变这一现状。 如…

Mysql数据库:索引管理

目录 一、索引的概述 1、索引的概念 2、索引的作用 3、索引的副作用 4、创建索引的原则依据 5、索引优化 6、索引的分类 7、数据文件与索引文件 二、管理数据库索引 1、查询索引 2、创建索引 2.1 创建普通索引 2.2 创建唯一索引 2.3 创建主键索引 2.4 创建组合…

《边缘计算:连接未来的智慧之桥》

随着物联网、5G等技术的快速发展&#xff0c;边缘计算作为一种新兴的计算模式&#xff0c;正逐渐引起人们的广泛关注。边缘计算通过将数据处理和存储功能放置在距离数据产生源头更近的位置&#xff0c;实现了更快速、更可靠的数据处理和交换&#xff0c;为各行各业带来了前所未…

【项目设计】基于MVC的负载均衡式的在线OJ

项目代码&#xff08;可直接下载运行&#xff09; 一、项目的相关背景 学习编程的小伙伴&#xff0c;大家对力扣、牛客或其他在线编程的网站一定都不陌生&#xff0c;这些编程网站除了提供了在线编程&#xff0c;还有其他的一些功能。我们这个项目只是做出能够在线编程的功能。…

音视频开发之旅(78)- Docker使用和交互流程

目录 1.Docker是什么 2.DockerFile的使用 3.常用命令 4.Docker和Web服务的交互流程 5.资料 一、Docker是什么 Docker通过轻量级的容器化技术&#xff0c;使得应用程序及其依赖可以打包在一个可移植的容器中运行&#xff0c;确保应用在不同环境下的一致性和效率。 1.1 核心…

Affiliate Stores: 建立营销联盟商店的详细教程- US Domain Center主机

第一步&#xff1a;了解营销联盟商店 营销联盟商店是一种电子商务模式&#xff0c;您可以在其中通过推广其他企业的产品或服务来赚取佣金。您在自己的网站上展示其他企业的产品&#xff0c;并在买家购买时获得佣金。通过 WooCommerce 平台&#xff0c;您可以轻松创建一个营销联…

PHP姓名快速匿名化工具(重组脱敏)

PHP姓名重组工具(脱敏/匿名化工具) 将excel数据姓名列粘贴提交&#xff0c;得到随机姓随机中间字随机尾字的重组姓名 那些年自用瞎搞的代码&#xff0c;今日整理成网页交提交得到结果的交互功能分享。 <?php //PHP姓名重组工具(脱敏/匿名化工具) //将excel数据姓名列粘贴…

第十二届蓝桥杯省赛CC++ 研究生组-路径

记录到每个结点的最短距离&#xff0c;以此为基础计算后续结点最优值 #include<iostream> #include<algorithm> using namespace std; typedef long long ll;ll gcd(int a, int b){if(!b) return a;return gcd(b, a % b); }int main(){ll dp[2022] {0};//dp[i]记…

Vue3 中应该使用 Ref 还是 Reactive?

一、引言 在Vue 3中&#xff0c;构建响应式数据结构是构建用户界面和交互体验的核心部分。而在创建这些响应式数据时&#xff0c;我们有两个主要工具&#xff1a;reactive和ref。选择使用哪一个&#xff0c;实际上取决于你的数据结构和访问需求。 reactive主要用于处理复杂的数…

Matlab|【免费】智能配电网的双时间尺度随机优化调度

目录 1 主要内容 基础模型 2 部分代码 3 部分程序结果 4 下载链接 1 主要内容 该程序为文章《Two-Timescale Stochastic Dispatch of Smart Distribution Grids》的源代码&#xff0c;主要做的是主动配电网的双时间尺度随机优化调度&#xff0c;该模型考虑配电网的高效和安…

【小白入门篇1】GPT到底是怎样练成?

由于具有代表性的OpenAI公司GPT模型并没有开源&#xff0c;所以本章节是参考一些开源和现有课程&#xff08;李宏毅&#xff09;讲解ChatGPT原理。本章没有涉及到很多数学运算&#xff0c;比较适合小白了解GPT到底是怎么练成。GPT的三个英文字母分别代表Generative(生成式)&…

了解交互设计:定义、解析及案例演示!

交互设计作为现代设计领域的一个重要分支&#xff0c;对用户体验和产品的成功至关重要。然而&#xff0c;许多人并不了解交互设计的定义和实践方法。本文将深入分析交互设计的概念和重要性&#xff0c;分享精彩的案例&#xff0c;推荐有用的交互设计工具&#xff0c;帮助您创造…

业务服务:redisson

文章目录 前言一、配置1. 添加依赖2. 配置文件/类3. 注入redission3. 封装工具类 二、应用1. RedisUtils工具类的基本使用 三、队列1. 工具类2. 普通队列3. 有界队列&#xff08;限制数据量&#xff09;4. 延迟队列&#xff08;延迟获取数据&#xff09;5. 优先队列&#xff08…

【Java多线程(1)】创建线程的几种方式和Thread类及其常见方法

目录 一、Java创建线程的方式 1. 通过继承 Thread 类实现多线程 2. 通过实现 Runnable 接口实现多线程 3. 其他变形 二、Thread类及常见方法 1. Thread类的常见构造方法 2. Thread类的几个常见属性 2.1 getName() 2.2 setDaemon() & isDaemon() 2.3 isAlive() …

HTML5+CSS3+移动web——CSS进阶

系列文章目录 HTML5CSS3移动web——HTML 基础-CSDN博客https://blog.csdn.net/ymxk2876721452/article/details/136070953?spm1001.2014.3001.5502HTML5CSS3移动web——列表、表格、表单-CSDN博客https://blog.csdn.net/ymxk2876721452/article/details/136221443?spm1001.20…

复习Day3

1231. 航班时间 - AcWing题库 #include<bits/stdc.h> using namespace std; int getTime(){//得到时间 int h1,m1,s1,h2,m2,s2,d0;scanf("%d:%d:%d %d:%d:%d (%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);//补匹配直接跳过 int timed*24*3…

【Django开发】0到1美多商城项目md教程第3篇:用户注册业务实现,1. 用户注册页面绑定Vue数据【附代码文档】

美多商城完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;欢迎来到美多商城&#xff01;&#xff0c;项目准备。展示用户注册页面&#xff0c;创建用户模块子应用。用户注册业务实现&#xff0c;用户注册前端逻辑。图形验证码&#xff0c;图形验证码接口设…

《自动机理论、语言和计算导论》阅读笔记:p1-p4

《自动机理论、语言和计算导论》学习第1天&#xff0c;p1-p4&#xff0c;总计4页。这只是个人的学习记录&#xff0c;因为很多东西不懂&#xff0c;难免存在理解错误的地方。 一、技术总结 1.有限自动机(finite automata)示例 1.software for checking digital circuits。 …