概念
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
例题
给定两个数a和b,计算出0~9在a和b之间出现的次数
源代码
# include <stdio.h>
void handle(int x, int n[]);
void handle(int x, int n[]);
int main(void)
{
int a, b;
int na[10];
int nb[10];
int i;
for(i = 0; i < 10; i++){
na[i] = 0;
nb[i] = 0;
}
scanf("%d%d", &a, &b);
if(a > b){ //确保a<b
a = a + b;
b = a - b;
a = a - b;
}
handle(a - 1, na);
handle(b, nb);
for(i = 0; i < 10; i++){
printf("%d出现%d次\n", i, nb[i] - na[i]);
}
return 0;
}
void handlex(int x, int n[])
{
if(x > 9){
n[x % 10] += 1;
handlex(x / 10, n);
} else{
n[x] += 1;
}
}
void handle(int x, int n[])
{
while(x-- > 0){
handlex(x, n);
}
}
分析
本程序简单的使用了分治和递归算法。其实把记录数字出现次数的数组声明为全局变量,就不用每次函数调用的时候传递了,代码会更简洁。
分享到:
相关推荐
学 习a c m 分 治算法 的入门 教程简单易学acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法vacm分治算法acm...
动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法.
分治算法求n个数的数组中找出第二个最大元素
赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf
分治算法是计算科学的一个经典算法,主要也是用了递归
分治算法的具体代码实现,能实现较好的排序效率
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
芯片测试:蛮力测试和分治策略都有写到,算法按设计与分析课的笔记,博主自己写的,仅仅参考了讲义的伪代码,若有错误请指出,谢谢。 重要的假设:好芯片至少比坏芯片多一片。 测试结果:奇数个芯片√ 偶数个芯片...
从键盘输入一组整数,通过分治算法求第二大的数
平面最近点对问题分治算法解答,C++实现,代码整洁规范。
分治算法在循环赛赛程分配中的应用算法设计与分析 分治算法 循环赛事
求整数数组内元素和的分治算法,用c++语言实现
分治算法教案 - 分治策略.ppt
分治算法分治算法分治算法分治算法分治算法
主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
第K小数,快速幂,下载之后负责答疑哦 int cmp(int x,int y) { return x; } void Swap() { swap(a[i],a[j]); swap(i,j); } void Operation(int START,int END) { i=START; j=END; while(i!...}
分治算法详解PPT课件.pptx
快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)
该课件讲述了分治算法的基本思想,并利用分治思想完成了对数组的排序,快速排序,数组选top k问题,讲解相邻点对的解决方案。
简要介绍了分治算法的实现和应用场景,原理和相关的背景