读书人

一步步学算法(算法例题)-1

发布时间: 2013-09-08 15:21:21 作者: rapoo

一步步学算法(算法题解)---1

本人大二,最近开始自学算法,在此记录自己学习过程中接触的习题。与君共勉。

水平有限,目前涉及的题目都比较水。

题目分布为5+1. 5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。



一步步学算法(算法题解)---1

数值处理相关问题。


1。19头牛int GetUglyNumber_Solution2(int index){ if(index <= 0) return 0; int *pUglyNumbers = new int[index]; pUglyNumbers[0] = 1; int nextUglyIndex = 1; int *pMultiply2 = pUglyNumbers; int *pMultiply3 = pUglyNumbers; int *pMultiply5 = pUglyNumbers; while(nextUglyIndex < index) { int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5); pUglyNumbers[nextUglyIndex] = min; while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex]) ++pMultiply2; while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex]) ++pMultiply3; while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex]) ++pMultiply5; ++nextUglyIndex; } int ugly = pUglyNumbers[nextUglyIndex - 1]; delete[] pUglyNumbers; return ugly;}int Min(int number1, int number2, int number3){ int min = (number1 < number2) ? number1 : number2; min = (min < number3) ? min : number3; return min;}
和第一种思路相比,这种算法不需要在非丑数的整数上做任何计算,因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)和GetUglyNumber_Solution2(1500)的运行时间。当然我们也要指出,第二种算法由于要保存已经生成的丑数,因此需要一个数组,从而需要额外的内存。第一种算法是没有这样的内存开销的。


1楼kongxiaoming2333昨天 21:01
请问平时看什么算法方面的书,求推荐

读书人网 >编程

热点推荐