今天上午上班由于没什么事做,就看看书,发现一个算法问题,开始看感觉貌似很简单,但是越想越有意思。
1,题目描述:
给定一个十进制的正整数N,写下从1开始到N所有出现“1”的个数。
例如:
N = 2 ,写下 1 ,2 。出现了一个1;
N = 12,写下1,2,3,4,5,6,7,8,9,10,11,12.这样1的个数是5;
问题是:
1,写一个函数f(N),返回1到N之间出现的1的个数,比如f(12) = 5.
2,在32位证书范围内,满足条件“f(N) = N”的最大的N是多少?
一开始我看到这个问题,第一反应就是递归,感觉只要解决两个问题就可以了,一是算出N含有的1的个数,再根据f(N-1)就能得到f(N)的值。其中f(1) = 1 ;这是一个最简单的递归方法。写出的代码如下:
public class Jeho1 {
public static int count1(int n){
if(n == 1 ) return 1;
else return count1(n-1)+Count1InOne(n);
}
public static int Count1InOne(int m){
int count = 0 ;
String temp = new Integer(m).toString();
for(int i = 0 ; i < temp.length() ; i ++){
if(temp.charAt(i) == '1') count++;
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
// for(int i = 1 ; i <= 99 ; i++){
// if(i == count1(i))
// System.out.println(i);
// }
System.out.println(count1(33));
}
}
刚开始我输入几个比较小点的数,发现算的都很正常,但是到了10k的时候就不行了,一看傻13了,栈溢出了。。。确实,这样递归看样子是不可能实现大数据计算的。没办法,只有继续看书寻求更好的方法。承认自己数学没有学好,看到这样的东西都不会望数据本身想,而总是想利用那些最基本的算法来实现。
书上的算法写的好复杂,简单来讲就是先从数字本来来找规律,数字的个位十位百位分开来看。由于被pdf加密,不能复制,所以自己就不太好来讲了,貌似可以上传附件,大家可以自己打开看看,这个是我按照它算法描述写的,果然计算结果就是不一样。代码献上先:
public class Jeho {
public static int count1(int n){
int count = 0 ;
int facror = 1;
int lowerNum = 0;
int currNum = 0 ;
int higherNum = 0;
while(n/facror != 0){
lowerNum = n - (n / facror) * facror;
currNum = (n / facror) % 10;
higherNum = n / (facror * 10);
switch(currNum){
case 0:
count += higherNum * facror;
break;
case 1:
count += higherNum * facror + lowerNum +1;
break;
default:
count += (higherNum + 1) * facror;
break;
}
facror *= 10;
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
int count = 0 ;
System.out.println(Integer.MAX_VALUE);
// System.out.println(count1(100000000));
for(int i = 1 ; i < 10000000 ; i++){
if(i == count1(i)){
count++;
}
}
System.out.println(count);
}
测试了下,输出一个结果超快,哎,自己脑子还是很不够用啊,得多多学习。
分享到:
相关推荐
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的...
在实际生产中,JSP并不总是要求得到精确解,因此有研究者使用近似算法在适当的时间内得到一个可接受的近似最优解来求解此问题,实际的计算表明,好的近似算法通常能在可接受的时间内得到与精确解相差甚小的近似解,...
设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于给定...
贪心算法 背包问题 c语言 绝对无误 运行成功
一个算法程序作业,利用C++实现卫兵布置问题
一个用贪心算法做的供参考
背包问题.本算法比较清晰,易读。...背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
(matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法...
算法是指解决问题的一种方法或过程 性质:1.输入:有零个或多个由外部提供的量作为算法的输入。 2.输出:算法产生至少一个量作为输出。
本算法用遗传算法和贪婪算法解决了背包问题,产生解得方法用贪婪算法,然后引入了一个错解的修复算法,搜索的时候用遗传算法。保证了快速收敛和解的完备性。包含源程序,算法介绍以及一份详细的报告,希望对读者有很...
用简单遗传算法求解8皇后问题,每次输出一代染色体中最好和最差个体的适应度,当求的解时便将解输出,解依次为0到7行哪一列放棋子,只是简单的熟悉一下遗传算法,代码没有写注释,如果有问题与我讨论就发邮件吧,...
遗传算法与优化问题 遗传算法与优化问题 遗传算法与优化问题
任务描述 (1) 利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。 例如:1美元=0.7英镑,1英镑=9.5...(2) 利用贪心算法的设计思想,设计一个解决该问题的算法。 (3)说明算法能产生最优解。
《迷茫的旅行商: 一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史,并阐述了其许多重要的应用范围,如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机的...
匈牙利算法指派问题matlab代码
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
分油问题 搜索算法 分油问题 搜索算法 分油问题 搜索算法 分油问题 搜索算法分油问题 搜索算法 分油问题 搜索算法
活动安排问题是利用贪心算法有效求解的很好例子。该问题要求高校的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法,使尽可能多的活动可以兼容的使用某一公共资源
15数码问题同八数码问题,是人工智能中一个很典型的智力问题。15数码问题是在4×4方格盘上,放有15个数码,剩下一个位置为空(方便起见,用0表示空),每一空格其上下左右的数码可移至空格。本问题给定初始位置和...