• 关于 INT10H可以做什么 的搜索结果

回答

递归4—递归的弱点 之所以没有把这段归为算法的讨论,因为这里讨论的不在是算法,而只是讨论一下滥用递归的不好的一面。 递归的用法似乎是很容易的,但是递归还是有她的致命弱点,那就是如果运用不恰当,滥用递归,程序的运行效率会非常的低,低到什么程度,低到出乎你的想像。当然,平时的小程序是看不出什么的,但是一旦在大项目里滥用递归,效率问题将引起程序的实用性的大大降低。 例子:求1到200的自然数的和。 第一种做法: #include <stdio.h> void main() { int i; int sum=0; for(i=1;i<=200;i++) { sum+=i; } printf("%d\n",sum); } 该代码中使用变量2个,计算200次。再看下个代码: #include <stdio.h> int add(int i) { if(i==1) { return i; } else { return i+add(i-1); } } void main() { int i; int sum=0; sum=add(200); printf("%d\n",sum); } 但看add()函数,每次调用要声明一个变量,每次调用要计算一次,所以应该是200个变量,200次计算,对比一下想想,如果程序要求递归次数非常多的时候,而且类似与这种情况,我们还能用递归去做吗。这个时候宁愿麻烦点去考虑其他办法,也要尝试摆脱递归的干扰。 21:21 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 程序算法5—递归3—递归的再次挖掘 递归的魅力就在于递归的代码,写出来实在是太简练了,而且能解决很多看起来似乎有规律但是又不是一下子能表达清楚的一些问题。思路清晰了,递归一写出来问题立即就解决了,给人一重感觉,递归这么好用。我们在此再更深的挖掘一下递归的用法。 之前再强调一点,也许有人会问,你前边的例子用递归似乎是更麻烦了。是,是麻烦了,因为为了方便理解,只能举一些容易理解的例子,一般等实际应用递归的时候,远远不是这种状态。 好了我们现在看一个数字的序列;有一组数的集合{1,2,4,7,11,16,22,29,37,46,56……}我故意多给几项,一般是只给前4项让你找规律的。序列给了,要求是求前50项的和。规律。有。还是没有。一看就象有,但是又看不出来,我多给了几项,应该很快看出来了,哦,原来每相邻的两项的差是个自然数排列,2-1=1,4-2=2,7-4=3,11-7=4,16-11=5…… 好了,把规律找出来了,一开始可能觉得没头绪,没问题,咱们把这个序列存放到一个数组总可以吧。那我们就声明一个数组,存放前50个数据,一个一个相加总可以了。于是有了下边的写法: #include <stdio.h> void main() { int i,a[50],sum=0; a[0]=1; for(i=1;i<50;i++) { a[i]=a[i-1]+i; } for(i=0;i<50;i++) { sum+=a[i]; } printf("%d\n",sum); } 好了,代码运行一下,结果出来了,正确不正确呢。自己测试吧,把50项改成1、2、3、4、5……项,试试前多少项是不是正确,虽然这不是正确的测试方法,但是的确是常用的测试方法。 等到这个代码已经完全理解了,完全明白了正个计算过程,我们就应该对这段代码进行改写优化了,毕竟这个代码还是不值得用一个数组的,那么我们尝试着只用变量去做一下: #include <stdio.h> void main() { int i; int number=1; int sum=0; for(i=0;i<50;i++) { number+=i; sum+=number; } printf("%d\n",sum); } 不知道我这样写是不是跨度大了点,但是我不准备详细解释了,很多东西需要你去认真分析的,所以很多东西如果不懂,自己想清楚比别人解释的效果会更好,因为别人讲只能让你理解,如果你自己去想,你就在理解的同时学会了思考。 这个代码写出来,不要继续看下去,先自己尝试着把这个题目用递归做一下看看自己能不能写出来,当然,递归并不是那么轻松就能使用的,有时候也是需要去细心设计的。如果做出来了,对比一下下边的代码,如果没有写出来,建议认真分析后边的代码,然后最好是能完全掌握,能自己随时把这行代码写出来: #include <stdio.h> int add(int n,int num,int i) { num+=i; if(i>=n-1) { return num; } else { return num+add(n,num,i+1); } } void main() { int sum; sum=add(50,1,0); /*50表示前50象项*/ printf("%d\n",sum); } 当然这个代码中的n只是一个参考变量,如果把if(i>=n-1)中的n该成50,那么就不需要这个n了,函数两个参数就可以了,这样写是为了修改方便。 20:28 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 程序算法4—递归2—递归的魅力 两天没有再写下去,因为毕竟有时候会有点心情问题,有时候觉得心情不好,一下子什么东西都想不起来了,很多时候写一些东西是需要状态的,一旦状态有了,想的东西才能顺利的写出来,虽然有些东西写出来在别人看来很垃圾,但是起码自己觉得还是相当满意的,我写这个本来就没有多少技术含量,只是想给初学程序的人一些指引,加快他们对程序的领悟。 好了,言归正传,继续上次递归的讨论,看看递归的魅力所在。 有这样一个问题,说一个猴子和一堆苹果,猴子一天吃一半,然后再吃一个,10天后剩下一个了,也就是说吃了10次,剩下1个了。问原来一共有多少苹果。 当然我们的目的不是求出苹果的数量,而是寻求一种解决问题的方法,这个问题一出来,通常对程序掌握深度不一样的朋友对这个题会有不同的认识,首先介绍一种解决方法,这种人脑袋还是比较聪明的,思路非常的明确,也有可能语言工具掌握的也不错,代码写出来非常准确,先看一下代码再做评价吧: #include <stdio.h> void main() { int day=10; int apple; int i,j; for(i=1;;i++) { apple=i; for(j=0;j<day;j++) { if(apple%2==0&&apple>0) { apple/=2; apple--; } else { break; } } if(j==day&&apple==1) { printf("%d\n",i); return; } } } 程序的大概思路很明确,简单介绍一下,这种写法就是从一个苹果开始算起,for(i=1;;i++)的作用就是改变苹果的数量,如果1个符合条件,那就试试2个,然后3个、4个一直到适合为止,里边的for循环就是把每一次取得的苹果的数目进行计算,如果每次都能顺利的被2整除(也就是说每次都能保证猴子能正好吃一半),然后再减一一直到最后,如果最后苹果剩下是一个而且天数正好是10天,那么就输出一下苹果的数目,整个程序退出,如果看不明白的没关系,这个写法非常的不适用,我们叫写出这种算法的人傻X,虽然这种人脑袋也挺聪明,能写出一些新鲜的写法,但是又脏又臭,代码既不简练又不高效。 所以说,有时候有些人以为自己学的很好了,自己所做的一切都是最好的,这种想法是不正确的,也许有些初学者没有什么经验写出来的代码却更让人容易明白点,那么也是先看看代码: #include <stdio.h> void main() { int day[11]; int i; day[0]=1; for(i=1;i<11;i++) { day[i]=(day[i-1]+1)*2; } printf("%d\n",day[10]); } 代码不长,而且也恰当的应用了题目中的规律,不是说要吃一半然后再吃一个吗。那我用数组来存放每天苹果的数量,用day[0]表示最后一天的苹果数量,那就是剩下的一个,然后就是找规律了,什么规律。就是如果猴子不多吃一个的话,那就是正好吃了一半,也就是说猴子当天吃了之后剩余的苹果的数目加1个然后再乘以2就是前一天的数目了,这样一想这个题目就简单的多了,于是这个题用数组就轻松的做出来了。 那么这个代码究竟是不是已经很好了呢,我们注意到,这里边每个数组元素只用了一次并没有被重复使用,再这种情况下我们是不是可以用一种方法代替数组呢。于是就有了更优化的写法,这个写法似乎已经是相当简练了: #include <stdio.h> void main() { int apple=1; int i; for(i=0;i<10;i++) { apple=(apple+1)*2; } printf("%d\n",apple); } 代码写到这里已经把问题完全抽象化了,所以我们就应该站在数学的角度去分析了。也许我们就应该结束了讨论,但是偏偏这个时候,又来了递归,悄悄的通过美丽的调用显示了一下她的魅力: #include <stdio.h> int apple(int i) { if(i==0) { return 1; } else { return (apple(i-1)+1)*2; } } void main() { int i; i=apple(10); printf("%d\n",i); } 原理都还是一样的,但是写出来的格式已经完全变掉了,没有了for循环。假想一个复杂的问题远比这个问题复杂,而且没有固定循环次数,那么我们再使用循环虽然也能解决问题,但是可能面临循环难以设计、控制等问题,这个时候用递归可能就会让问题变的非常的清晰。 另外说一点,一般我这里的代码,并不是从最差到最好的,基本排列是从最差到最合适的代码(当然是本人认为最合适的,也许还有更好的,本人能力所限了),然后最后给出一种比较违反常规的代码,一般是不赞成用最后一种代码的,当然有时候最后一种代码也许是最好的选择,看情况吧。 20:25 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet 10月15日 程序算法3—递归1—递归小显威力 现在用C语言实现一个字符串的倒序输出,当然,方法也是很多的,但是如果程序中能有相对优化的方法或者简单明了易读的方法,那对你自己或者别人都是一种幸福。 第一种写法,这类写法既浪费内存又不实用,一般是刚学程序的才这样做,程序的结构很简单,利用的是数组: #include <stdio.h> void main() { char c[2000]; int i,length=0; for(i=0;i<2000;i++) { scanf("%c",&c[i]); if(c[i]=='\n') { break; } else { length++; } } for(i=length;i>0;i--) { printf("%c",c[i-1]); } printf("\n"); } 这段代码中的数组,声明大了浪费内存空间,声明小了又怕不够,所以写这种代码的人一般写完之后会祈祷,祈祷测试的人不要输入的太多,太多就不能完全显示了。 与其这么提心吊胆,于是又有人想出了第二种方法,终于解决了一些问题,而且完全实现了程序的实际要求,于是,这种人经过一番苦想,觉得问题终于可以解决了,这种方法看起来是一种很不错的方法。 #include <stdio.h> #include <malloc.h> void main() { int i; char *c; c=(char *)malloc(1*sizeof(char)); for(i=0;;i++) { *(c+i)=getchar(); if(*(c+i)=='\n') { *(c+i)='\0'; break; } else c=(char *)realloc(c,(i+2)*sizeof(char)); } for(--i;i>=0;i--) { putchar(*(c+i)); } printf("\n"); free(c); } 怎么样。不错,准确的应用内存,几乎没有浪费什么空间,这种方法也体现了一下指针的强大功能,写这个程序虽然不敢说这个人已经掌握了指针的应用,但是起码可以说他已经会用指针了。代码写出来,看起来已经有点美感。 但是也有一些人还是比较喜欢动脑筋的,经过一番思考,终于想出了第三种比较容易写的方法,也许有写初学者可能觉得有些难度,但是事实上这个东西一点都不难,如果稍微有点程序功底之后再看这段代码,应该是相当轻松。 #include <stdio.h> void run() { char c; c=getchar(); if(c!='\n') { run(); } else { return; } putchar(c); } void main() { run(); printf("\n"); } 写出的代码让人眼前一亮,哇。原来递归功能简单而又好用,那我们为什么不好好利用呢。但是递归也不一定就是最好的选择,因为有时候虽然递归用起来很方便,但是效率却不高,以后的讨论中还会详细说明。

一键天涯 2019-12-02 01:24:01 0 浏览量 回答数 0

回答

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将给出详细的说明。 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。 现在,让我们开始吧: 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include <iostream.h> void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义: 若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的。。。) 现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因,我们通常都是通过循环次数来对比算法。 2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[j]<pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法: 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中选择最小的与第二个交换,这样往复下去。 #include <iostream.h> void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(int j=i+1;j<Count;j++) { if(pData[j]<iTemp) { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次 其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法: 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include <iostream.h> void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0) && (iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次 其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些,所以我们浪费了时间。 最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。 1.快速排序: #include <iostream.h> void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } void QuickSort(int* pData,int Count) { run(pData,0,Count-1); } void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。 2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。 第一层递归,循环n次,第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变 成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全 不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。 如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢于快速排序(因为要重组堆)。 三、其他排序 1.双向冒泡: 通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。 代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。 反正我认为这是一段有趣的代码,值得一看。 #include <iostream.h> void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1; //反向的部分 for(i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } right = t-1; }while(left<=right); } void main() { int data[] = {10,9,8,7,6,5,4}; Bubble2Sort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 2.SHELL排序 这个排序非常复杂,看了程序就知道了。 首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。 工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序 以次类推。 #include <iostream.h> void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1; int iTemp; int k,s,w; for(int i=0;i<4;i++) { k = step[i]; s = -k; for(int j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp<pData[w]) && (w>=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } } void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++) cout<<data[i]<<" "; cout<<"\n"; } 呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因 避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。 四、基于模板的通用排序: 这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。 MyData.h文件 /////////////////////////////////////////////////////// class CMyData { public: CMyData(int Index,char* strData); CMyData(); virtual ~CMyData(); int m_iIndex; int GetDataSize(){ return m_iDataSize; }; const char* GetData(){ return m_strDatamember; }; //这里重载了操作符: CMyData& operator =(CMyData &SrcData); bool operator <(CMyData& data ); bool operator >(CMyData& data ); private: char* m_strDatamember; int m_iDataSize; }; //////////////////////////////////////////////////////// MyData.cpp文件 //////////////////////////////////////////////////////// CMyData::CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) { } CMyData::~CMyData() { if(m_strDatamember != NULL) delete[] m_strDatamember; m_strDatamember = NULL; } CMyData::CMyData(int Index,char* strData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) { m_iDataSize = strlen(strData); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,strData); } CMyData& CMyData::operator =(CMyData &SrcData) { m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,SrcData.GetData()); return *this; } bool CMyData::operator <(CMyData& data ) { return m_iIndex<data.m_iIndex; } bool CMyData::operator >(CMyData& data ) { return m_iIndex>data.m_iIndex; } /////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// //主程序部分 #include <iostream.h> #include "MyData.h" template <class T> void run(T* pData,int left,int right) { int i,j; T middle,iTemp; i = left; j = right; //下面的比较都调用我们重载的操作符函数 middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } template <class T> void QuickSort(T* pData,int Count) { run(pData,0,Count-1); } void main() { CMyData data[] = { CMyData(8,"xulion"), CMyData(7,"sanzoo"), CMyData(6,"wangjun"), CMyData(5,"VCKBASE"), CMyData(4,"jacky2000"), CMyData(3,"cwally"), CMyData(2,"VCUSER"), CMyData(1,"isdong") }; QuickSort(data,8); for (int i=0;i<8;i++) cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; cout<<"\n"; }

沉默术士 2019-12-02 01:19:06 0 浏览量 回答数 0

问题

第6篇 指针数组字符串(下):报错

kun坤 2020-06-08 11:01:44 4 浏览量 回答数 1

新用户福利专场,云服务器ECS低至102元/年

新用户专场,1核2G 102元/年起,2核4G 699.8元/年起

问题

十大经典排序算法最强总结(内含代码实现)

游客pklijor6gytpx 2020-01-09 14:44:55 1240 浏览量 回答数 2

问题

什么样的手段处理图片后会使得用java取得该图片的RGB值与实际值不同?报错

因为相信,所以看见。 2020-05-27 12:59:32 6 浏览量 回答数 1

问题

memcache proxy之memagent介绍分析 实现分析 一致性hash?400报错

爱吃鱼的程序员 2020-06-05 12:21:05 0 浏览量 回答数 1

回答

关于二十四点游戏的编程思路与基本算法 漫长的假期对于我来说总是枯燥无味的,闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单,就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。但是其中却不乏一些有趣的题目,这不,我们刚玩了一会儿,便遇到了一个难题——3、6、6、10(其实后来想想,这也不算是个太难的题,只是当时我们的脑筋都没有转弯而已,呵呵)。 问题既然出现了,我们当然要解决。冥思苦想之际,我的脑中掠过一丝念头——何不编个程序来解决这个问题呢。文曲星中不就有这样的程序吗。所以这个想法应该是可行。想到这里我立刻开始思索这个程序的算法,最先想到的自然是穷举法(后来发现我再也想不到更好的方法了,悲哀呀,呵呵),因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举,不就可以利用这个计算程序来完成这个计算二十四点的程序吗。确定了这个思路之后,我开始想这个问题的细节。 首先穷举的可行性问题。我把表达式如下分成三类—— 1、 无括号的简单表达式。 2、 有一个括号的简单表达式。 3、 有两个括号的较复4、 杂表达式。 穷举的开始我对给出的四个数进行排列,其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列,算法如下: /* ans[] 用来存放各种排列组合的数组 */ /* c[] 存放四张牌的数组 */ /* k[] c[]种四张牌的代号,其中k[I]=I+1。 用它来代替c[]做处理,考虑到c[]中有可能出现相同数的情况 */ /* kans[] 暂存生成的排列组合 */ /* j 嵌套循环的次数 */ int fans(c,k,ans,kans,j) int j,k[],c[];char ans[],kans[]; { int i,p,q,r,h,flag,s[4],t[4][4]; for(p=0,q=0;p<4;p++) { for(r=0,flag=0;r if(k[p]!=kans[r]) flag++; if(flag==j) t[j][q++]=k[p]; } for(s[j]=0;s[j]<4-j;s[j]++) { kans[j]=t[j][s[j>; if(j==3) { for(h=0;h<4;h++) ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表 达式中的位置 */ for(h=0;h<3;h++) symbol(ans,h); /* 在表达式中添加运算符号 */ } else { j++; fans(c,k,ans,kans,j); j--; } } } 正如上面函数中提到的,在完成四张牌的排列之后,在表达式中添加运算符号。由于只有四张牌,所以只要添加三个运算符号就可以了。由于每一个运算符号可重复,所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举,算法如下: /* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/ int sans(ans,sy,j,h) char ans[],sy[];int j,h; { int i,p,k[3],m,n; char ktans[20]; for(k[j]=0;k[j]<4;k[j]++) { ans[2*j+1]=sy[k[j>; /* 刚才的四个数分别存放在0、2、4、6位 这里的三个运算符号分别存放在1、3、5位*/ if(j==2) { ans[5]=sy[k[j>; /* 此处根据不同的表达式形式再进行相应的处理 */ } else } } 好了,接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类,是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种,无括号自然不用另行处理;而第二种情况由以下代码可以得出其可能性有六种,其中还有一种是多余的。 for(m=0;m<=4;m+=2) for(n=m+4;n<=8;n+=2) 这个for循环给出了添加一个括号的可能性的种数,其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0,n=8,也就是放在表达式的两端。这真是多此一举,呵呵。最后一种情况是添加两个括号,我分析了一下,发现只可能是这种形式才不会是重复的——(a b)(c d)。为什么不会出现嵌套括号的情况呢。因为如果是嵌套括号,那么外面的括号肯定是包含三个数字的(四个没有必要),也就是说这个括号里面包含了两个运算符号,而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的,则肯定可以通过一些转换去掉括号(你不妨举一些例子来试试),也就是说这一个括号没有必要;如果这两个运算符号不是同一优先级,也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高,自然就没有必要在它的外面添加括号了。 综上所述,所有可能的表达式的种数为24*64*(1+6+1)=12288种。哈哈,只有一万多种可能性(这其中还有重复),这对于电脑来说可是小case哟。所以,对于穷举的可行性分析和实现也就完成了。 接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用,那么什么是栈呢。栈的概念是从日常生活中货物在货栈种的存取过程抽象出来的,即最后存放入栈的货物(堆在靠出口处)先被提取出去,符合“先进后出,后进先出”的原则。这种结构犹如子弹夹。 在栈中,元素的插入称为压入(push)或入栈,元素的删除称为弹出(pop)或退栈。 栈的基本运算有三种,其中包括入栈运算、退栈运算以及读栈顶元素,这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。 那么作为栈的著名应用,表达式的计算可以有两种方法。 第一种方法—— 首先建立两个栈,操作数栈OVS和运算符栈OPS。其中,操作数栈用来记忆表达式中的操作数,其栈顶指针为topv,初始时为空,即topv=0;运算符栈用来记忆表达式中的运算符,其栈顶指针为topp,初始时,栈中只有一个表达式结束符,即topp=1,且OPS(1)=‘;’。此处的‘;’即表达式结束符。 然后自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W做如下不同的处理: 1、 若W为操作数 2、 则将W压入操作数栈OVS 3、 且继续扫描下一个字符 4、 若W为运算符 5、 则根据运算符的性质做相应的处理: (1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS,并继续扫描下一个字符。 (2)、若运算符W为表达式结束符‘;’且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=’;’),则处理过程结束,此时,操作数栈栈顶元素(即OVS(topv))即为表达式的值。 (3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)=’(‘),则将左括号从运算符栈谈出,且继续扫描下一个符号。 (4)、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp)),则从操作数栈OVS中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈OPS中弹出一个运算符,设为+,然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。 第二种方法—— 首先对表达式进行线性化,然后将线性表达式转换成机器指令序列以便进行求值。 那么什么是表达式的线性化呢。人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式,有时必须借助括号才能将运算顺序表达清楚,而且处理也比较复杂。 1929年,波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation)。波兰表达式的特点是运算符位于运算对象的后面,因此称为后缀表示。在对波兰表达式进行运算,严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。 表达式 波兰表达式 A-B AB- (A-B)*C+D AB-C*D+ A*(B+C/D)-E*F ABCD/+*EF*- (B+C)/(A-D) BC+AD-/ OK,所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式,利用栈可以把表达式变换成波兰表达式,也可以利用栈来计算波兰表达式的值。 至于转换和计算的过程和第一种方法大同小异,这里就不再赘述了。 下面给出转换和计算的具体实现程序—— /* first函数给出各个运算符的优先级,其中=为表达式结束符 */ int first(char c) { int p; switch(c) { case '*': p=2; break; case '/': p=2; break; case '+': p=1; break; case '-': p=1; break; case '(': p=0; break; case '=': p=-1; break; } return(p); } /* 此函数实现中缀到后缀的转换 */ /* M的值宏定义为20 */ /* sp[]为表达式数组 */ int mid_last() { int i=0,j=0; char c,sm[M]; c=s[0]; sm[0]='='; top=0; while(c!='\0') { if(islower(c)) sp[j++]=c; else switch(c) { case '+': case '-': case '*': case '/': while(first(c)<=first(sm[top])) sp[j++]=sm[top--]; sm[++top]=c; break; case '(': sm[++top]=c; break; case ')': while(sm[top]!='(') sp[j++]=sm[top--]; top--; break; default :return(1); } c=s[++i]; } while(top>0) sp[j++]=sm[top--]; sp[j]='\0'; return(0); } /* 由后缀表达式来计算表达式的值 */ int calc() { int i=0,sm[M],tr; char c; c=sp[0]; top=-1; while(c!='\0') { if(islower(c)) sm[++top]=ver[c-'a'];/*在转换过程中用abcd等来代替数, 这样才可以更方便的处理非一位数, ver数组中存放着这些字母所代替的数*/ else switch(c) { case '+': tr=sm[top--]; sm[top]+=tr; break; case '-': tr=sm[top--]; sm[top]-=tr; break; case '*': tr=sm[top--]; sm[top]*=tr; break; case '/': tr=sm[top--];sm[top]/=tr;break; default : return(1); } c=sp[++i]; } if(top>0) return(1); else } 这样这个程序基本上就算解决了,回过头来拿这个程序来算一算文章开始的那个问题。哈哈,算出来了,原来如此简单——(6-3)*10-6=24。 最后我总结了一下这其中容易出错的地方—— 1、 排列的时候由于一个数只能出现一次, 所以必然有一个判断语句。但是用什么来判断,用大小显然不行,因为有可能这四个数中有两个或者以上的数是相同的。我的方法是给每一个数设置一个代号,在排列结束时,通过这个代号找到这个数。 2、在应用嵌套函数时,需仔细分析程序的执行过程,并对个别变量进行适当的调整(如j的值),程序才能正确的执行。 3、在分析括号问题的时候要认真仔细,不要错过任何一个可能的机会,也要尽量使程序变得简单一些。不过我的分析可能也有问题,还请高手指点。 4、在用函数对一个数组进行处理的时候,一定要注意如果这个数组还需要再应用,就必须将它先保存起来,否则会出错,而且是很严重的错误。 5、在处理用户输入的表达式时,由于一个十位数或者更高位数是被分解成各位数存放在数组中,所以需对它们进行处理,将它们转化成实际的整型变量。另外,在转化过程中,用一个字母来代替这个数,并将这个数存在一个数组中,且它在数组中的位置和代替它的这个字母有一定的联系,这样才能取回这个数。 6、由于在穷举过程难免会出现计算过程中有除以0的计算,所以我们必须对calc函数种对于除的运算加以处理,否则程序会因为出错而退出(Divide by 0)。 7、最后一个问题,本程序尚未解决。对于一些比较著名的题目,本程序无法解答。比如说5、5、5、1或者8、8、3、3。这是由于这些题目在计算的过程用到了小数,而本程序并没有考虑到小数。

知与谁同 2019-12-02 01:22:19 0 浏览量 回答数 0

问题

第6篇 指针数组字符串(下)补充:报错

kun坤 2020-06-08 11:02:03 3 浏览量 回答数 1

问题

不同的 linux 系统版本 udp 返回的数据不同

问问小秘 2020-01-09 18:04:32 5 浏览量 回答数 1

回答

你发的这些东西看不出问题, 这只不过是设置SDL音频播放参数和回调接口而已. 得看看你是如何解码的, 有没有把解码出来的数据弄丢, 不然是不会有噪音的...######我把源码发上来了 你帮我看一下 拜托了######回复 @bruce_hou : 没看到你的代码, 我也不知道怎么回事.######具体怎么处理啊 能不能详细的说一下######我把源码发上来 #include "libavformat/avformat.h" #include "libswscale/swscale.h" #include <SDL/SDL.h> #include <SDL/SDL_thread.h> #ifdef main #undef main #endif #include <stdio.h> #include <math.h> #define SDL_AUDIO_BUFFER_SIZE 1024 #define MAX_AUDIOQ_SIZE (5 * 16 * 1024) #define MAX_VIDEOQ_SIZE (5 * 256 * 1024) #define AV_SYNC_THRESHOLD 0.01 #define AV_NOSYNC_THRESHOLD 10.0 #define FF_ALLOC_EVENT (SDL_USEREVENT) #define FF_REFRESH_EVENT (SDL_USEREVENT + 1) #define FF_QUIT_EVENT (SDL_USEREVENT + 2) #define VIDEO_PICTURE_QUEUE_SIZE 1 typedef struct PacketQueue { AVPacketList *first_pkt, *last_pkt; int nb_packets; int size; SDL_mutex *mutex; SDL_cond *cond; } PacketQueue; typedef struct VideoPicture { SDL_Overlay *bmp; int width, height; int allocated; double pts; } VideoPicture; typedef struct VideoState { AVFormatContext *pFormatCtx; int videoStream, audioStream; double audio_clock; AVStream *audio_st; PacketQueue audioq; uint8_t audio_buf[(AVCODEC_MAX_AUDIO_FRAME_SIZE * 3) / 2]; unsigned int audio_buf_size; unsigned int audio_buf_index; AVPacket audio_pkt; uint8_t *audio_pkt_data; int audio_pkt_size; int audio_hw_buf_size; double frame_timer; double frame_last_pts; double frame_last_delay; double video_clock; ///<pts of last decoded frame / predicted pts of next decoded frame AVStream *video_st; PacketQueue videoq; VideoPicture pictq[VIDEO_PICTURE_QUEUE_SIZE]; int pictq_size, pictq_rindex, pictq_windex; SDL_mutex *pictq_mutex; SDL_cond *pictq_cond; SDL_Thread *parse_tid; SDL_Thread *video_tid; char filename[1024]; int quit; } VideoState; SDL_Surface *screen; VideoState *global_video_state; void packet_queue_init(PacketQueue *q) { memset(q, 0, sizeof(PacketQueue)); q->mutex = SDL_CreateMutex(); q->cond = SDL_CreateCond(); } int packet_queue_put(PacketQueue *q, AVPacket *pkt) { AVPacketList *pkt1; if(av_dup_packet(pkt) < 0) { return -1; } pkt1 = (AVPacketList *)av_malloc(sizeof(AVPacketList)); if (!pkt1) return -1; pkt1->pkt = *pkt; pkt1->next = NULL; SDL_LockMutex(q->mutex); if (!q->last_pkt) q->first_pkt = pkt1; else q->last_pkt->next = pkt1; q->last_pkt = pkt1; q->nb_packets++; q->size += pkt1->pkt.size; SDL_CondSignal(q->cond); SDL_UnlockMutex(q->mutex); return 0; } static int packet_queue_get(PacketQueue *q, AVPacket *pkt, int block) { AVPacketList *pkt1; int ret; SDL_LockMutex(q->mutex); for(;;) { if(global_video_state->quit) { ret = -1; break; } pkt1 = q->first_pkt; if (pkt1) { q->first_pkt = pkt1->next; if (!q->first_pkt) q->last_pkt = NULL; q->nb_packets--; q->size -= pkt1->pkt.size; *pkt = pkt1->pkt; av_free(pkt1); ret = 1; break; } else if (!block) { ret = 0; break; } else { SDL_CondWait(q->cond, q->mutex); } } SDL_UnlockMutex(q->mutex); return ret; } double get_audio_clock(VideoState *is) { double pts; int hw_buf_size, bytes_per_sec, n; pts = is->audio_clock; hw_buf_size = is->audio_buf_size - is->audio_buf_index; bytes_per_sec = 0; n = is->audio_st->codec->channels * 2; if(is->audio_st) { bytes_per_sec = is->audio_st->codec->sample_rate * n; } if(bytes_per_sec) { pts -= (double)hw_buf_size / bytes_per_sec; } return pts; } int audio_decode_frame(VideoState *is, uint8_t *audio_buf, int buf_size, double *pts_ptr) { int len1, data_size, n; AVPacket *pkt = &is->audio_pkt; double pts; for(;;) { while(is->audio_pkt_size > 0) { data_size = buf_size; len1 = avcodec_decode_audio2(is->audio_st->codec, (int16_t *)audio_buf, &data_size, is->audio_pkt_data, is->audio_pkt_size); if(len1 < 0) { is->audio_pkt_size = 0; break; } is->audio_pkt_data += len1; is->audio_pkt_size -= len1; if(data_size <= 0) { continue; } pts = is->audio_clock; *pts_ptr = pts; n = 2 * is->audio_st->codec->channels; is->audio_clock += (double)data_size / (double)(n * is->audio_st->codec->sample_rate); return data_size; } if(pkt->data) av_free_packet(pkt); if(is->quit) { return -1; } if(packet_queue_get(&is->audioq, pkt, 1) < 0) { return -1; } is->audio_pkt_data = pkt->data; is->audio_pkt_size = pkt->size; if(pkt->pts != AV_NOPTS_VALUE) { is->audio_clock = av_q2d(is->audio_st->time_base)*pkt->pts; } } } void audio_callback(void *userdata, Uint8 *stream, int len) { VideoState *is = (VideoState *)userdata; int len1, audio_size; double pts; while(len > 0) { if(is->audio_buf_index >= is->audio_buf_size) { audio_size = audio_decode_frame(is, is->audio_buf, sizeof(is->audio_buf), &pts); if(audio_size < 0) { is->audio_buf_size = 1024; memset(is->audio_buf, 0, is->audio_buf_size); } else { is->audio_buf_size = audio_size; } is->audio_buf_index = 0; } len1 = is->audio_buf_size - is->audio_buf_index; if(len1 > len) len1 = len; memcpy(stream, (uint8_t *)is->audio_buf + is->audio_buf_index, len1); len -= len1; stream += len1; is->audio_buf_index += len1; } } static Uint32 sdl_refresh_timer_cb(Uint32 interval, void *opaque) { SDL_Event event; event.type = FF_REFRESH_EVENT; event.user.data1 = opaque; SDL_PushEvent(&event); return 0; } static void schedule_refresh(VideoState *is, int delay) { SDL_AddTimer(delay, sdl_refresh_timer_cb, is); } void video_display(VideoState *is) { SDL_Rect rect; VideoPicture *vp; AVPicture pict; float aspect_ratio; int w, h, x, y; int i; vp = &is->pictq[is->pictq_rindex]; if(vp->bmp) { if(is->video_st->codec->sample_aspect_ratio.num == 0) { aspect_ratio = 0; } else { aspect_ratio = av_q2d(is->video_st->codec->sample_aspect_ratio) * is->video_st->codec->width / is->video_st->codec->height; } if(aspect_ratio <= 0.0) { aspect_ratio = (float)is->video_st->codec->width / (float)is->video_st->codec->height; } h = screen->h; w = ((int)(h * aspect_ratio)) & -3; if(w > screen->w) { w = screen->w; h = ((int)(w / aspect_ratio)) & -3; } x = (screen->w - w) / 2; y = (screen->h - h) / 2; rect.x = x; rect.y = y; rect.w = w; rect.h = h; SDL_DisplayYUVOverlay(vp->bmp, &rect); } } void video_refresh_timer(void *userdata) { VideoState *is = (VideoState *)userdata; VideoPicture *vp; double actual_delay, delay, sync_threshold, ref_clock, diff; if(is->video_st) { if(is->pictq_size == 0) { schedule_refresh(is, 1); } else { vp = &is->pictq[is->pictq_rindex]; delay = vp->pts - is->frame_last_pts; if(delay <= 0 || delay >= 1.0) { delay = is->frame_last_delay; } is->frame_last_delay = delay; is->frame_last_pts = vp->pts; ref_clock = get_audio_clock(is); diff = vp->pts - ref_clock; sync_threshold = (delay > AV_SYNC_THRESHOLD) ? delay : AV_SYNC_THRESHOLD; if(fabs(diff) < AV_NOSYNC_THRESHOLD) { if(diff <= -sync_threshold) { delay = 0; } else if(diff >= sync_threshold) { delay = 2 * delay; } } is->frame_timer += delay; actual_delay = is->frame_timer - (av_gettime() / 1000000.0); if(actual_delay < 0.010) { actual_delay = 0.010; } schedule_refresh(is, (int)(actual_delay * 1000 + 0.5)); video_display(is); if(++is->pictq_rindex == VIDEO_PICTURE_QUEUE_SIZE) { is->pictq_rindex = 0; } SDL_LockMutex(is->pictq_mutex); is->pictq_size--; SDL_CondSignal(is->pictq_cond); SDL_UnlockMutex(is->pictq_mutex); } } else { schedule_refresh(is, 100); } } void alloc_picture(void *userdata) { VideoState *is = (VideoState *)userdata; VideoPicture *vp; vp = &is->pictq[is->pictq_windex]; if(vp->bmp) { // we already have one make another, bigger/smaller SDL_FreeYUVOverlay(vp->bmp); } // Allocate a place to put our YUV image on that screen vp->bmp = SDL_CreateYUVOverlay(is->video_st->codec->width, is->video_st->codec->height, SDL_YV12_OVERLAY, screen); vp->width = is->video_st->codec->width; vp->height = is->video_st->codec->height; SDL_LockMutex(is->pictq_mutex); vp->allocated = 1; SDL_CondSignal(is->pictq_cond); SDL_UnlockMutex(is->pictq_mutex); } int queue_picture(VideoState *is, AVFrame *pFrame, double pts) { VideoPicture *vp; //int dst_pix_fmt; AVPicture pict; SDL_LockMutex(is->pictq_mutex); while(is->pictq_size >= VIDEO_PICTURE_QUEUE_SIZE && !is->quit) { SDL_CondWait(is->pictq_cond, is->pictq_mutex); } SDL_UnlockMutex(is->pictq_mutex); if(is->quit) return -1; // windex is set to 0 initially vp = &is->pictq[is->pictq_windex]; if(!vp->bmp || vp->width != is->video_st->codec->width || vp->height != is->video_st->codec->height) { SDL_Event event; vp->allocated = 0; event.type = FF_ALLOC_EVENT; event.user.data1 = is; SDL_PushEvent(&event); SDL_LockMutex(is->pictq_mutex); while(!vp->allocated && !is->quit) { SDL_CondWait(is->pictq_cond, is->pictq_mutex); } SDL_UnlockMutex(is->pictq_mutex); if(is->quit) { return -1; } } static struct SwsContext *img_convert_ctx; if (img_convert_ctx == NULL) { img_convert_ctx = sws_getContext(is->video_st->codec->width, is->video_st->codec->height, is->video_st->codec->pix_fmt, is->video_st->codec->width, is->video_st->codec->height, PIX_FMT_YUV420P, SWS_BICUBIC, NULL, NULL, NULL); if (img_convert_ctx == NULL) { fprintf(stderr, "Cannot initialize the conversion context\n"); exit(1); } } if(vp->bmp) { SDL_LockYUVOverlay(vp->bmp); //dst_pix_fmt = PIX_FMT_YUV420P; pict.data[0] = vp->bmp->pixels[0]; pict.data[1] = vp->bmp->pixels[2]; pict.data[2] = vp->bmp->pixels[1]; pict.linesize[0] = vp->bmp->pitches[0]; pict.linesize[1] = vp->bmp->pitches[2]; pict.linesize[2] = vp->bmp->pitches[1]; // Convert the image into YUV format that SDL uses sws_scale(img_convert_ctx, pFrame->data, pFrame->linesize, 0, is->video_st->codec->height, pict.data, pict.linesize); SDL_UnlockYUVOverlay(vp->bmp); vp->pts = pts; if(++is->pictq_windex == VIDEO_PICTURE_QUEUE_SIZE) { is->pictq_windex = 0; } SDL_LockMutex(is->pictq_mutex); is->pictq_size++; SDL_UnlockMutex(is->pictq_mutex); } return 0; } double synchronize_video(VideoState *is, AVFrame *src_frame, double pts) { double frame_delay; if(pts != 0) { is->video_clock = pts; } else { pts = is->video_clock; } frame_delay = av_q2d(is->video_st->codec->time_base); frame_delay += src_frame->repeat_pict * (frame_delay * 0.5); is->video_clock += frame_delay; return pts; } uint64_t global_video_pkt_pts = AV_NOPTS_VALUE; int our_get_buffer(struct AVCodecContext *c, AVFrame *pic) { int ret = avcodec_default_get_buffer(c, pic); uint64_t *pts = (uint64_t *)av_malloc(sizeof(uint64_t)); *pts = global_video_pkt_pts; pic->opaque = pts; return ret; } void our_release_buffer(struct AVCodecContext *c, AVFrame *pic) { if(pic) av_freep(&pic->opaque); avcodec_default_release_buffer(c, pic); } int video_thread(void *arg) { VideoState *is = (VideoState *)arg; AVPacket pkt1, *packet = &pkt1; int len1, frameFinished; AVFrame *pFrame; double pts; pFrame = avcodec_alloc_frame(); for(;;) { if(packet_queue_get(&is->videoq, packet, 1) < 0) { // means we quit getting packets break; } pts = 0; // Save global pts to be stored in pFrame in first call global_video_pkt_pts = packet->pts; // Decode video frame len1 = avcodec_decode_video(is->video_st->codec, pFrame, &frameFinished, packet->data, packet->size); if(packet->dts == AV_NOPTS_VALUE && pFrame->opaque && *(uint64_t*)pFrame->opaque != AV_NOPTS_VALUE) { pts = *(uint64_t *)pFrame->opaque; } else if(packet->dts != AV_NOPTS_VALUE) { pts = packet->dts; } else { pts = 0; } pts *= av_q2d(is->video_st->time_base); // Did we get a video frame? if(frameFinished) { pts = synchronize_video(is, pFrame, pts); if(queue_picture(is, pFrame, pts) < 0) { break; } } av_free_packet(packet); } av_free(pFrame); return 0; } int stream_component_open(VideoState *is, int stream_index) { AVFormatContext *pFormatCtx = is->pFormatCtx; AVCodecContext *codecCtx; AVCodec *codec; SDL_AudioSpec wanted_spec, spec; if(stream_index < 0 || stream_index >= pFormatCtx->nb_streams) { return -1; } // Get a pointer to the codec context for the video stream codecCtx = pFormatCtx->streams[stream_index]->codec; if(codecCtx->codec_type == CODEC_TYPE_AUDIO) { // Set audio settings from codec info wanted_spec.freq = codecCtx->sample_rate; wanted_spec.format = AUDIO_S16SYS; wanted_spec.channels = codecCtx->channels; wanted_spec.silence = 0; wanted_spec.samples = SDL_AUDIO_BUFFER_SIZE; wanted_spec.callback = audio_callback; wanted_spec.userdata = is; if(SDL_OpenAudio(&wanted_spec, &spec) < 0) { fprintf(stderr, "SDL_OpenAudio: %s\n", SDL_GetError()); return -1; } is->audio_hw_buf_size = spec.size; } codec = avcodec_find_decoder(codecCtx->codec_id); if(!codec || (avcodec_open(codecCtx, codec) < 0)) { fprintf(stderr, "Unsupported codec!\n"); return -1; } switch(codecCtx->codec_type) { case CODEC_TYPE_AUDIO: is->audioStream = stream_index; is->audio_st = pFormatCtx->streams[stream_index]; is->audio_buf_size = 0; is->audio_buf_index = 0; memset(&is->audio_pkt, 0, sizeof(is->audio_pkt)); packet_queue_init(&is->audioq); SDL_PauseAudio(0); break; case CODEC_TYPE_VIDEO: is->videoStream = stream_index; is->video_st = pFormatCtx->streams[stream_index]; is->frame_timer = (double)av_gettime() / 1000000.0; is->frame_last_delay = 40e-3; packet_queue_init(&is->videoq); is->video_tid = SDL_CreateThread(video_thread, is); codecCtx->get_buffer = our_get_buffer; codecCtx->release_buffer = our_release_buffer; break; default: break; } return 0; } int decode_interrupt_cb(void) { return (global_video_state && global_video_state->quit); } int decode_thread(void *arg) { VideoState *is = (VideoState *)arg; AVFormatContext *pFormatCtx; AVPacket pkt1, *packet = &pkt1; int video_index = -1; int audio_index = -1; int i; is->videoStream=-1; is->audioStream=-1; global_video_state = is; // will interrupt blocking functions if we quit! url_set_interrupt_cb(decode_interrupt_cb); // Open video file if(av_open_input_file(&pFormatCtx, is->filename, NULL, 0, NULL)!=0) return -1; // Couldn't open file is->pFormatCtx = pFormatCtx; // Retrieve stream information if(av_find_stream_info(pFormatCtx)<0) return -1; // Couldn't find stream information // Dump information about file onto standard error dump_format(pFormatCtx, 0, is->filename, 0); // Find the first video stream for(i=0; i<pFormatCtx->nb_streams; i++) { if(pFormatCtx->streams[i]->codec->codec_type==CODEC_TYPE_VIDEO && video_index < 0) { video_index=i; } if(pFormatCtx->streams[i]->codec->codec_type==CODEC_TYPE_AUDIO && audio_index < 0) { audio_index=i; } } if(audio_index >= 0) { stream_component_open(is, audio_index); } if(video_index >= 0) { stream_component_open(is, video_index); } if(is->videoStream < 0 || is->audioStream < 0) { fprintf(stderr, "%s: could not open codecs\n", is->filename); goto fail; } // main decode loop for(;;) { if(is->quit) { break; } // seek stuff goes here if(is->audioq.size > MAX_AUDIOQ_SIZE || is->videoq.size > MAX_VIDEOQ_SIZE) { SDL_Delay(10); continue; } if(av_read_frame(is->pFormatCtx, packet) < 0) { if(url_ferror(pFormatCtx->pb) == 0) { SDL_Delay(100); continue; } else { break; } } // Is this a packet from the video stream? if(packet->stream_index == is->videoStream) { packet_queue_put(&is->videoq, packet); } else if(packet->stream_index == is->audioStream) { packet_queue_put(&is->audioq, packet); } else { av_free_packet(packet); } } while(!is->quit) { SDL_Delay(100); } fail: { SDL_Event event; event.type = FF_QUIT_EVENT; event.user.data1 = is; SDL_PushEvent(&event); } return 0; } int main(int argc, char *argv[]) { SDL_Event event; VideoState *is; is = (VideoState *)av_mallocz(sizeof(VideoState)); if(argc < 2) { fprintf(stderr, "Usage: test <file>\n"); exit(1); } // Register all formats and codecs av_register_all(); if(SDL_Init(SDL_INIT_VIDEO | SDL_INIT_AUDIO | SDL_INIT_TIMER)) { fprintf(stderr, "Could not initialize SDL - %s\n", SDL_GetError()); exit(1); } // Make a screen to put our video #ifndef __DARWIN__ screen = SDL_SetVideoMode(640, 480, 0, 0); #else screen = SDL_SetVideoMode(640, 480, 24, 0); #endif if(!screen) { fprintf(stderr, "SDL: could not set video mode - exiting\n"); exit(1); } //pstrcpy(is->filename, sizeof(is->filename), argv[1]); strcpy(is->filename,argv[1]); is->pictq_mutex = SDL_CreateMutex(); is->pictq_cond = SDL_CreateCond(); schedule_refresh(is, 40); is->parse_tid = SDL_CreateThread(decode_thread, is); if(!is->parse_tid) { av_free(is); return -1; } for(;;) { SDL_WaitEvent(&event); switch(event.type) { case FF_QUIT_EVENT: case SDL_QUIT: is->quit = 1; SDL_Quit(); exit(0); break; case FF_ALLOC_EVENT: alloc_picture(event.user.data1); break; case FF_REFRESH_EVENT: video_refresh_timer(event.user.data1); break; default: break; } } return 0; } 你帮我看一下######你有没有最新的ffmpeg转码示范代码啊######回复 @Jack.arain : 给我一个示范代码好不,这上面的代码是一个示范代码,我把 avcodec_decode_audio3,######看了下代码, 不知道你用的是哪个版本的ffmpeg, 但你这个代码是非常老的了, 另外, 在ffmpeg后期的版本中, avcodec_decode_audio函数可能解码出来的数据要比实际的数据要长, 需要使用av_samples_get_buffer_size来获得实际大小.###### C++我不懂,不过音视频解码的内核我写过不少。如果内核解别的不出错,那么噪音基本来源于输出的音频PCM的BUF不干净或者输入的频段信息有缺失,某个通道没有数据进入。前者你的输出BUF可能被别的代码(包括解码本身)写操作过。你查下有没有内存泄露的问题。后者,是你的输入不全的问题。更大概率是后者。前者要定期加入噪音的概率还是比较小。 这类问题的检测方法是外围做最简单的调用。验证调用方法和内核模块都没有问题。然后再堆叠其他系统模块上去。 ######的确是旧的代码,现在新的都用上了avcodec_decode_audio4了,你的ffmpeg库是什么版本的,新的版本有libswresample,可以帮你的音频做重采样,这样播放出来就不会有噪声了,如果想看事例代码,就看你的ffmpeg源码里的ffplay.c吧,里面的接口都和你的ffmpeg对应的,看看人家是怎么处理音频的,希望对你有用。

爱吃鱼的程序员 2020-06-05 13:33:51 0 浏览量 回答数 0

回答

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法,即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法(Iterative Method)。 一般可以做如下定义:对于给定的线性方程组x=Bx+f(这里的x、B、f同为矩阵,任意线性方程组都可以变换成此形式),用公式x(k+1)=Bx(k)+f(括号中为上标,代表迭代k次得到的x,初始时k=0)逐步带入求近似解的方法称为迭代法(或称一阶定常迭代法)。如果k趋向无穷大时limx(k)存在,记为x*,称此迭代法收敛。显然x*就是此方程组的解,否则称为迭代法发散。 跟迭代法相对应的是直接法(或者称为一次解法),即一次性的快速解决问题,例如通过开方解决方程x +3= 4。一般如果可能,直接解法总是优先考虑的。但当遇到复杂问题时,特别是在未知量很多,方程为非线性时,我们无法找到直接解法(例如五次以及更高次的代数方程没有解析解,参见阿贝耳定理),这时候或许可以通过迭代法寻求方程(组)的近似解。 最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。 利用迭代算法解决问题,需要做好以下三个方面的工作: 确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以顺推或倒推的方法来完成。 对迭代过程进行控制 在 什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数 是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需 要进一步分析出用来结束迭代过程的条件。 举例 例 1 :一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析:这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u(n - 1)× 2 (n ≥ 2) 对应 u n 和 u(n - 1),定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 :阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析:根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 (x 的初值为第 15 次分裂之后的个数 2^20) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end ps:java中幂的算法是Math.pow(2,20);返回double,稍微注意一下 例 3 :验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1。如此经过有限次运算后,总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析:定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为:n=1。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法开平方: #include<stdio.h> #include<math.h> void main() { double a,x0,x1; printf("Input a:\n"); scanf("%lf",&a);//为什么在VC6.0中不能写成“scanf("%f",&a);”。 if(a<0) printf("Error!\n"); else { x0=a/2; x1=(x0+a/x0)/2; do { x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-6); } printf("Result:\n"); printf("sqrt(%g)=%g\n",a,x1); } 求平方根的迭代公式:x1=1/2*(x0+a/x0)。 算法:1.先自定一个初值x0,作为a的平方根值,在我们的程序中取a/2作为a的初值;利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差很大。 ⒉把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1. ⒊利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。 ⒋比较前后两次求得的平方根值x0和x1,如果它们的差值小于我们指定的值,即达到我们要求的精度,则认为x1就是a的平方根值,去执行步骤5;否则执行步骤2,即循环进行迭代。 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: ⑴ 选一个方程的近似根,赋给变量x0; ⑵ 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ⑶ 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤⑵的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while (fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: ⑴ 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; ⑵ 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib⑴=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问 题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算 fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib⑴和fib(0),分别能 立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib⑴和fib(0)后,返回得到fib⑵的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为:⑴5、4、3 ⑵5、4、2 ⑶5、4、1 ⑷5、3、2 ⑸5、3、1 ⑹5、2、1 ⑺4、3、2 ⑻4、3、1 ⑼4、2、1 ⑽3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递 归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并 保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达 到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止 当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: ⑴ 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 ⑵ 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是 从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选 解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在 候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。 对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv tw=tw; twv tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv tw; tv=twv tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); }

云篆 2019-12-02 01:25:10 0 浏览量 回答数 0

问题

[IBM DW] 用 inotify 监控 Linux 文件系统事件:报错

kun坤 2020-06-07 16:43:37 0 浏览量 回答数 1

问题

【今日算法】备战大厂必备题目,持续更新

游客ih62co2qqq5ww 2020-04-08 09:21:40 3542 浏览量 回答数 4

回答

ConvertOfficeFormat 该接口实现 OFFICE 文档格式的转换,用于文档打印、预览等场景。 它采用 同步请求 方式执行,执行完毕返回转换成功的页数。注意,同步转换超时时间为 5秒,如果大于 5秒 的转换需要使用异步接口 CreateOfficeConversionTask 。 请求参数 名称 类型 是否必填 描述 Project String 是 项目名 Action String 是 ConvertOfficeFormat SrcUri String 是 源数据的存储位置, OSS 资源采用如下格式”oss://bucket1/object” SrcType String 否 源数据的后缀类型,当前文档转换根据 OSS 对象的后缀名来确定源数据类型,当 OSS 对象没有后缀名时,可以设置该值 TgtType String 是 转换输出目标文件类型: vector,转成向量文件,需要使用 js 引擎来进行渲染 png,转成 png 格式的图片文件 jpg,转成 jpg 格式的图片文件 pdf,转成 pdf 文件 text,转成只包含文本内容的文件,主要用来提取文件的文本内容,注意只支持演示和表格文件类型 TgtUri String 是 转换输出内容到目标位置,建议 TgtUri 和 SrcUri 在同一个桶,便于权限管理 例如 OSS 桶的指定前缀”oss://bucket1/converttasks/session123/“ Password String 否 Office 文档的打开密码,如果需要转换有密码的文档,请设置该字段 StartPage int 否 从第 x 页开始转换,默认为1 EndPage int 否 转换至第 x 页,默认为200,如果需要转换全部页,设置为-1 MaxSheetRow int 否 表格文件转换最大行数,默认为1000。如果需要转换所有行,设置为-1 MaxSheetCol int 否 表格文件转换最大列数,默认为100,如果需要转换所有行,设置为-1 MaxSheetCount int 否 表格文件转换最多 sheet 数,如果需要转换所有Sheet,设置为-1 FitToPagesTall bool 否 表格文件转 pdf 时,将行全部输出到一页,默认为 false,只有设置 TgtType 为 pdf 时才会生效 FitToPagesWide bool 否 表格文件转 pdf 时,将列全部输出在一页,默认为 false,只有设置 TgtType 为 pdf 时才会生效 TgtFilePrefix String 否 转换后的文件名称前缀,在目标类型为 jpg, png, pdf 时才生效,可以是英文,数字,横划线,下划线,长度不超过256个字符,参考自定义目标文件名称 TgtFileSuffix String 否 转换后的文件名称后缀,在目标类型为 jpg, png, pdf 时才生效,可以是英文,数字,横划线,下划线,点号,长度不超过256个字符,参考自定义目标文件名称 TgtFilePages String 否 转换后输出指定文件页数,在目标类型为 jpg, png, pdf时才生效,默认输出所有页。例如:[1, 2, 100],只会输出1,2,100页到 TgtUri,最多指定100个页数,如果超过100页,请分多次转换进行提交 PdfVector bool 否 pdf 转换成 vector 时,是否使用向量模式,默认为 false true:使用向量模式,预览效果比较清晰,转换耗时较长 false:使用图片模式,预览效果一般,转换耗时较短 Hidecomments bool 否 word, ppt 转换成 vector, jpg, png 时,是否隐藏批注和应用修订,默认为 false true:隐藏批注,应用修订 false:显示批注和修订 DisplayDpi int 否 转换 jpg,png 时,设置图片分辨率,取值范围[96, 2048] 目前支持的 输入文件类型 包含如下 48 种格式: 演示文件:pptx、ppt、pot、potx、pps、ppsx、dps、dpt、pptm、potm、ppsm。 表格文件:xls、xlt、et、ett、xlsx、xltx、csv、xlsb、xlsm、xltm。 文字文件:doc、dot、wps、wpt、docx、dotx、docm、dotm。 其他格式文件: pdf、 lrc、 c、 cpp、 h、 asm、 s、 java、 asp、 bat、 bas、 prg、 cmd、 rtf、 txt、 log、 xml、 htm、 html。 目前支持的 输出文件类型 有如下 4 种: vector 向量模式,使用智能媒体管理产品提供的 前端渲染引擎,更好的支持翻页、缩放。 jpg 模式,按文件样式每页生成一张 jpg 图片。 png 模式,按文件样式每页生成一张 png 图片。 pdf 模式,每个文件生成一个 pdf 文件。 text 模式,按文件样式每页生成一个 text 文件 返回参数 名称 类型 描述 RequestId String 用户发送的每次接口调用请求,无论成功与否,系统都会返回一个唯一识别码 RequestId 给用户 PageCount Integer 转换成功的页数 基于TgtUri返回TgtLoc,在OSS对象存储中的命名规则 基于 TgtUri 参数指定的前缀,比如/bucket1/imm-format-convert-tgt/session123/,根据转换目标类型的不同,那么生成的目标文件也有所不同: 目标类型为 vector 时 如果源文件为非 excel 类型 /bucket1/imm-format-convert-tgt/session123/doc/meta.json /bucket1/imm-format-convert-tgt/session123/doc/fp1.json /bucket1/imm-format-convert-tgt/session123/doc/fp2.json /bucket1/imm-format-convert-tgt/session123/doc/fp[...].json /bucket1/imm-format-convert-tgt/session123/doc/I/1 /bucket1/imm-format-convert-tgt/session123/doc/I/2 /bucket1/imm-format-convert-tgt/session123/doc/I/[...] 如果源文件为 excel 类型 /bucket1/imm-format-convert-tgt/session123/doc/meta.json /bucket1/imm-format-convert-tgt/session123/doc/s1/meta.json /bucket1/imm-format-convert-tgt/session123/doc/s1/fp1.json /bucket1/imm-format-convert-tgt/session123/doc/s1/fp2.json /bucket1/imm-format-convert-tgt/session123/doc/s1/fp[...].json /bucket1/imm-format-convert-tgt/session123/doc/s2/meta.json /bucket1/imm-format-convert-tgt/session123/doc/s2/fp1.json /bucket1/imm-format-convert-tgt/session123/doc/s2/fp2.json /bucket1/imm-format-convert-tgt/session123/doc/s2/fp[...].json /bucket1/imm-format-convert-tgt/session123/doc/s[...] /meta.json /bucket1/imm-format-convert-tgt/session123/doc/s[...]/fp1.json /bucket1/imm-format-convert-tgt/session123/doc/s[...]/fp2.json /bucket1/imm-format-convert-tgt/session123/doc/s[...]/fp[...].json 注意:vector 模式需要使用特定的 js 引擎进行渲染。 目标类型为 jpg 时 如果源文件为非 excel 类型 /bucket1/imm-format-convert-tgt/session123/1.jpg /bucket1/imm-format-convert-tgt/session123/2.jpg /bucket1/imm-format-convert-tgt/session123/[...].jpg 如果源文件为 excel 类型 /bucket1/imm-format-convert-tgt/session123/s1/1.jpg /bucket1/imm-format-convert-tgt/session123/s1/2.jpg /bucket1/imm-format-convert-tgt/session123/s1/[...].jpg /bucket1/imm-format-convert-tgt/session123/s2/1.jpg /bucket1/imm-format-convert-tgt/session123/s2/2.jpg /bucket1/imm-format-convert-tgt/session123/s2/[...].jpg /bucket1/imm-format-convert-tgt/session123/s[...]/1.jpg /bucket1/imm-format-convert-tgt/session123/s[...]/2.jpg /bucket1/imm-format-convert-tgt/session123/s[...]/[...].jpg 注意:源文件为 excel 类型时,会先根据 excel 的表格数,生成对应数量的文件夹,再在对应的文件夹下,生成对应数量的 jpg 文件 目标类型为 png 时 如果源文件为非 excel 类型 /bucket1/imm-format-convert-tgt/session123/1.png /bucket1/imm-format-convert-tgt/session123/2.png /bucket1/imm-format-convert-tgt/session123/[...].png 如果源文件为 excel 类型 /bucket1/imm-format-convert-tgt/session123/s1/1.png /bucket1/imm-format-convert-tgt/session123/s1/2.png /bucket1/imm-format-convert-tgt/session123/s1/[...].png /bucket1/imm-format-convert-tgt/session123/s2/1.png /bucket1/imm-format-convert-tgt/session123/s2/2.png /bucket1/imm-format-convert-tgt/session123/s2/[...].png /bucket1/imm-format-convert-tgt/session123/s[...]/1.png /bucket1/imm-format-convert-tgt/session123/s[...]/2.png /bucket1/imm-format-convert-tgt/session123/s[...]/[...].png 注意:源文件为 excel 类型时,会先根据 excel 的表格数,生产对应数量的文件夹,再在对应的文件夹下,生成对应数量的 png 文件 目标类型为 pdf 时 /bucket1/imm-format-convert-tgt/session123/1.pdf 注意:转换 pdf 时,无论源文件是什么类型,都只会生成一个 pdf 文件 目标类型为 text 时 /bucket1/imm-format-convert-tgt/session123/1.text /bucket1/imm-format-convert-tgt/session123/2.text /bucket1/imm-format-convert-tgt/session123/[...].text 注意:只支持演示类型和文字类型的源文件 重复请求处理 基于幂等性的要求, 两次相同操作以最后执行的请求为准。 如果两次执行操作的内容相同或者重复请求(内容相同,SignatureNonce 也相同),并且系统已经存在该任务,则后续的请求直接返回成功,避免消耗计算资源做相同的任务。 转换生成目标文件 生成的目标文件会持久化保存,推荐为某个桶下的 /imm-format-convert-tgt/${name} 路径,从而便于维护管理。 您可以主动删除转换后的目标文件,如果不主动删除则会长期保留以备使用,但是会占用存储空间。如果希望自动的删除目标文件,您也可以在 /imm-format-convert-tgt 前缀下配置 OSS 的生命周期,这样目标文件在到期后,会根据策略被清除。 自定义目标文件名称 当前文档转换通过设置 TgtFilePrefix 和 TgtFileSuffix 来支持自定义文件名称 假设 TgtType 为 jpg,则目标文件名称规则如下: TgtFilePrefix 和 TgtFileSuffix 都为空的条件下,目标文件名称为:[x].jpg TgtFilePrefix 为空,TgtFileSuffix 为 aa,则目标文件名称为:[x]aa TgtFilePrefix 为 aa,TgtFileSuffix 为空,则目标文件名称为:aa[x] TgtFilePrefix 为 aa,TgtFileSuffix 为 bb,则目标文件名称为:aa[x]bb 备注:[x] 表示多个目标文件,从1开始,如果转换后的文件有8页,则所有的目标文件为: aa[1]bb, aa[2]bb, …, aa[8]bb 示例 请求示例 POST https://imm.cn-shanghai.aliyuncs.com ?Action=ConvertOfficeFormat &Project=test &SrcUri="oss://bucket1/test.pptx" &TgtType=vector &TgtUri="oss://bucket1/imm-format-convert-tgt/session123/" ... 此处的示例,目的是展示关键参数,还需要其他的公共参数才能正常调用,推荐使用 SDK 来发送 API。 成功返回示例 { "RequestId": "FF3B7D81-66AE-47E0-BF69-157DCF187514", "PageCount": 10 } 特殊错误码 如果转换出错,在返回的 JSON 中会包含如下字段 { "RequestId": "7DA1FCD1-004C-4EB4-B039-C6BBDCEB0701", "HostId": "imm.cn-shanghai.aliyuncs.com", "Code": "DocumentConvertFailed.NeedPassword", "Message": "The conversion has been failed, need password to open file." } 错误代码 说明 OSSAccessError OSS 访问失败,请检查 SrcUri,TgtUri 对应的 bucket,路径是否存在,所在 Region 是否和 IMM Region 一致 InvalidParameter.SrcType.NotSupported 不支持的文件类型,当前文档转换根据文件后缀名来判断文件类型,请检查文件后缀名,SrcType 参数 DocumentConvertFailed.ExceedFileSizeLimit 当前文档转换默认支持 40 MB 文件大小,超过该大小的文件转换时会抛出该错误 DocumentConvertFailed.OpenFileError 转换时,打开文件失败,请检查源文档后缀和内容是否匹配 DocumentConvertFailed.ExportFileError 转换时,处理文件内容失败,请检查源文档是否能够正常打开 DocumentConvertFailed.NeedPassword 该文档需要密码才能打开,请设置 Password 参数 ExecutionTimeout 执行超时,请检查文档大小,页数,如果确实需要转换,请使用异步接口 CreateOfficeConversionTask InternalError 内部错误,请开工单并提供 RequestId

1934890530796658 2020-03-31 12:46:55 0 浏览量 回答数 0

问题

SSH面试题

琴瑟 2019-12-01 21:46:22 3489 浏览量 回答数 0

问题

深入理解Magento – 第六章 – 高级Magento模型 :报错

kun坤 2020-06-14 15:19:25 0 浏览量 回答数 1

问题

深入理解Magento – 第六章 – 高级Magento模型:配置报错 

kun坤 2020-06-02 14:47:07 2 浏览量 回答数 1

问题

深入理解Magento – 第六章 – 高级Magento模型 - Magento报错

montos 2020-06-03 20:30:01 2 浏览量 回答数 1

问题

OracleASM管理

男刊 2019-12-01 21:33:34 7934 浏览量 回答数 2

回答

把配置文件拿出来看看? ###### 引用来自“李玉珏”的评论把配置文件拿出来看看? <?xml version="1.0" encoding="UTF8"?> <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:util="http://www.springframework.org/schema/util" xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd http://www.springframework.org/schema/util http://www.springframework.org/schema/util/spring-util.xsd"> <bean id="ignite.cfg" class="org.apache.ignite.configuration.IgniteConfiguration"> <!-- Set to true to enable distributed class loading for examples, default is false. --> <property name="peerClassLoadingEnabled" value="true"/> <property name="discoverySpi"> <bean class="org.apache.ignite.spi.discovery.tcp.TcpDiscoverySpi"> <property name="ipFinder"> <!-- Ignite provides several options for automatic discovery that can be used instead os static IP based discovery. For information on all options refer to our documentation: http://apacheignite.readme.io/docs/cluster-config --> <!-- Uncomment static IP finder to enable static-based discovery of initial nodes. --> <!--<bean class="org.apache.ignite.spi.discovery.tcp.ipfinder.vm.TcpDiscoveryVmIpFinder">--> <bean class="org.apache.ignite.spi.discovery.tcp.ipfinder.multicast.TcpDiscoveryMulticastIpFinder"> <property name="addresses"> <list> <!-- In distributed environment, replace with actual host IP address. --> <value>127.0.0.1:48500..48509</value> </list> </property> </bean> </property> </bean> </property> <!-- Explicitly configure TCP communication SPI changing local port number for the nodes from the first cluster. --> <property name="communicationSpi"> <bean class="org.apache.ignite.spi.communication.tcp.TcpCommunicationSpi"> <property name="localPort" value="48100"/> </bean> </property> <!-- Enable task execution events for examples. --> <property name="includeEventTypes"> <list> <!--Task execution events--> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_STARTED"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_FINISHED"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_FAILED"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_TIMEDOUT"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_SESSION_ATTR_SET"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_TASK_REDUCED"/> <!--Cache events--> <util:constant static-field="org.apache.ignite.events.EventType.EVT_CACHE_OBJECT_PUT"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_CACHE_OBJECT_READ"/> <util:constant static-field="org.apache.ignite.events.EventType.EVT_CACHE_OBJECT_REMOVED"/> </list> </property> </bean> <bean id="igniteCacheFactory" class="com.ignite.IgniteCacheFactory"> <constructor-arg index="0" ref="typesMap" /> <constructor-arg index="1" ref="queryEntitiesMap" /> <constructor-arg index="2" ref="ignite.cfg" /> <constructor-arg index="3" value="REPLICATED" /> </bean> <bean id="typesMap" class="com.ignite.TypesMap"> <property name="list"> <list> <bean class="org.apache.ignite.cache.store.jdbc.JdbcType"> <property name="databaseSchema" value="mishu"/> <property name="databaseTable" value="cert_aqrz_copy"/> <property name="keyType" value="com.toubiaomishu.mojo.CertAqrzCopyKey"/> <property name="valueType" value="com.toubiaomishu.mojo.CertAqrzCopy"/> <property name="keyFields"> <list> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="srcUUid"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="srcuuid"/> </bean> </list> </property> <property name="valueFields"> <list> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="srcUUid"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="srcuuid"/> </bean> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="secureLevel"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="securelevel"/> </bean> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="secureRank"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="securerank"/> </bean> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="yxqTime"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="yxqtime"/> </bean> <bean class="org.apache.ignite.cache.store.jdbc.JdbcTypeField"> <property name="databaseFieldType"> <util:constant static-field="java.sql.Types.VARCHAR"/> </property> <property name="databaseFieldName" value="zhUUid"/> <property name="javaFieldType" value="java.lang.String"/> <property name="javaFieldName" value="zhuuid"/> </bean> </list> </property> </bean> </list> </property> </bean> <bean id="queryEntitiesMap" class="com.ignite.QueryEntitiesMap"> <property name="list"> <list> <bean class="org.apache.ignite.cache.QueryEntity"> <property name="keyType" value="com.toubiaomishu.mojo.CertAqrzCopyKey"/> <property name="valueType" value="com.toubiaomishu.mojo.CertAqrzCopy"/> <property name="fields"> <util:map map-class="java.util.LinkedHashMap"> <entry key="srcuuid" value="java.lang.String"/> <entry key="securelevel" value="java.lang.String"/> <entry key="securerank" value="java.lang.String"/> <entry key="yxqtime" value="java.lang.String"/> <entry key="zhuuid" value="java.lang.String"/> </util:map> </property> <property name="indexes"> <list> <bean class="org.apache.ignite.cache.QueryIndex"> <property name="name" value="PRIMARY"/> <property name="indexType"> <util:constant static-field="org.apache.ignite.cache.QueryIndexType.SORTED"/> </property> <property name="fields"> <map> <entry key="srcuuid" value="true"/> </map> </property> </bean> <bean class="org.apache.ignite.cache.QueryIndex"> <property name="name" value="srcUUid"/> <property name="indexType"> <util:constant static-field="org.apache.ignite.cache.QueryIndexType.SORTED"/> </property> <property name="fields"> <map> <entry key="srcuuid" value="true"/> <entry key="yxqtime" value="true"/> <entry key="zhuuid" value="true"/> </map> </property> </bean> </list> </property> </bean> </list> </property> </bean> <!-- Datasource for sample in-memory mysql database. --> <bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource" destroy-method="close"> <property name="driverClassName" value="com.mysql.jdbc.Driver"/> <property name="url" value="jdbc:mysql://localhost:3306/mishu?useUnicode=true&characterEncoding=UTF-8&zeroDateTimeBehavior=convertToNull"/> <property name="username" value="root"/> <property name="password" value="5201128blue"/> <!-- 连接池启动时的初始值 --> <property name="initialSize" value="10"/> <!-- 连接池的最大值 --> <property name="maxActive" value="100"/> <!-- 最大空闲值.当经过一个高峰时间后,连接池可以慢慢将已经用不到的连接慢慢释放一部分,一直减少到maxIdle为止 --> <property name="maxIdle" value="10"/> <!-- 最小空闲值.当空闲的连接数少于阀值时,连接池就会预申请去一些连接,以免洪峰来时来不及申请 --> <property name="minIdle" value="5"/> <property name="removeAbandoned" value="true"/> <property name="removeAbandonedTimeout" value="10"/> <property name="testWhileIdle"> <value>true</value> </property> <property name="testOnBorrow"> <value>true</value> </property> <property name="testOnReturn"> <value>true</value> </property> <property name="validationQuery"> <value>SELECT 1</value> </property> <property name="validationQueryTimeout"> <value>1</value> </property> <property name="timeBetweenEvictionRunsMillis"> <value>3600000</value> </property> <property name="minEvictableIdleTimeMillis"> <value>60000</value> </property> <property name="numTestsPerEvictionRun"> <value>5</value> </property> </bean> </beans> package com.ignite; import org.apache.ignite.Ignite; import org.apache.ignite.IgniteCache; import org.apache.ignite.Ignition; import org.apache.ignite.cache.CacheMode; import org.apache.ignite.cache.QueryEntity; import org.apache.ignite.cache.store.jdbc.CacheJdbcPojoStoreFactory; import org.apache.ignite.cache.store.jdbc.JdbcType; import org.apache.ignite.configuration.CacheConfiguration; import org.apache.ignite.configuration.IgniteConfiguration; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.beans.factory.annotation.Qualifier; import org.springframework.stereotype.Service; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; //这个类根据JdbcType和QueryEntity创建缓存 public class IgniteCacheFactory { public IgniteCacheFactory(TypesMap typesMap,QueryEntitiesMap queryEntitiesMap,IgniteConfiguration conf,CacheMode cacheMode){ init(typesMap.getList(),queryEntitiesMap,conf,cacheMode); } public void init(List<JdbcType> list,QueryEntitiesMap queryEntitiesMap,IgniteConfiguration conf,CacheMode cacheMode) { CacheConfiguration[] cacheConflist = new CacheConfiguration[list.size()]; for(int i=0;i<list.size();i++){ JdbcType qe=list.get(i); String cacheName=qe.getDatabaseTable(); qe.setCacheName(cacheName); String valueType=qe.getValueType(); CacheConfiguration cfg=IgniteCacheConfigurationFactory.create(cacheName); CacheJdbcPojoStoreFactory sf= new CacheJdbcPojoStoreFactory(); sf.setDataSourceBean("dataSource"); sf.setTypes(qe); cfg.setCacheMode(cacheMode);//CacheMode.PARTITIONED cfg.setCacheStoreFactory(sf); cacheConflist[i]=cfg; List<QueryEntity> qlist=new ArrayList<>(); qlist.add(queryEntitiesMap.get(valueType)); cfg.setQueryEntities(qlist); } conf.setCacheConfiguration(cacheConflist); System.out.println("----------------->>------------------"); } } ######你开启那么多事件做什么呢?###### 调用任务代码,先加载,在执行分布式任务: public static void main(String[] args) throws IgniteException{ //Ignition.setClientMode(true); Ignite ignite=Ignition.start("ignite2.xml"); IgniteCluster cluster = ignite.cluster(); // 启动之后调用,直接加载所有定的表数据进缓存 Object[] list= (Object[]) ignite.cacheNames().toArray(); for(int i=0;i<list.length;i++){ String cacheName=String.valueOf(list[i]); IgniteCache cahce= ignite.cache(cacheName); cahce.loadCache(null); } CreditCalculate c=new CreditCalculate(); c.setGc(3); c.setSc(5); c.setGb(new BigDecimal(20)); c.setSb(new BigDecimal(20)); c.setSqlstr("(SELECT.... THEN ...."); c.setAq("1"); c.setIdd(new BigDecimal(3)); c.setProjTy("房程"); c.setXydjDqq("xydjDqq"); IgniteCompute compute = ignite.compute(cluster.forRemotes()); // Execute task on the clustr and wait for its completion. List<String> cnt = compute.execute(CreditCalculateTask.class,c); //System.out.println(">>> Total number of characters in the phrase is '" + cnt.size() + "'."); //System.out.println(">>>"+ cnt.get(0)); System.out.println("----------------mapreduce end-------------------"); } ###### 引用来自“李玉珏”的评论把配置文件拿出来看看? 半夜醒来:会不会是因为我缓存是在任务外声明的,所以执行任务是引用都是同一台机器上的缓存 // Inject Ignite instance. @IgniteInstanceResource private Ignite ignite; IgniteCache certSrcCache = ignite.cache("cert_src");//******这里声明 @Override public List<ComputeJob> split(int gridSize, CreditCalculate arg) { List<ComputeJob> jobs = new ArrayList<>(); SqlQuery sql2 = new SqlQuery(CertSrc.class, "from ..."); QueryCursor<Cache.Entry<Long, CertSrc>> companyList = certSrcCache.query(sql2); ... for (Cache.Entry<Long, CertSrc> e : companyList) { jobs.add(new ComputeJobAdapter() { @Override public Object execute() { .... SqlFieldsQuery sql = new SqlFieldsQuery(sql1); try (QueryCursor<List<?>> cursor = certSrcCache.query(sql)) {//*******这里在ComputeJobAdapter内部引用 ######回复 @fir01 : 如果默认的端口被占用的话,会使用一个随机的端口,我估计你看看节点启动时的控制台输出应该会有的。######回复 @fir01 : 任务数没有数量限制,这个看你的内存配置了。######回复 @李玉珏 : 端口好像是随机的,怎么从本机访问远程机器的h2控制台,或者在哪里配置固定的端口呢?######回复 @李玉珏 : 谢谢回复。好像是搞定了,估计mapReduce有bug或者要配置,在ubuntu里面就是单线程的,windows是多线程。换executorService就都可以异步多线程了,但是ubuntu里面执行看打印还是会执行一会就停个6秒,为什么呢?是不是存放任务的队列有大小限制?任务总数10823######回复 @fir01 : SHARED是默认的部署模式。###### 我想我还要测试一下是不是我本机发送任务速度慢。7519个任务1秒钟就发送完毕。######任务数不要太多,你可以换一个维度,控制下任务的总数量,大量的任务处于排队状态,是很占用资源的。######都是用ignite自己的broadcast方法异步发布任务就又快又流畅,无卡顿现象。看样子非官方的,说可以用的东西最好别用。

kun坤 2020-06-06 23:16:57 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 SSL证书 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站 2020中国云原生 阿里云云栖号