MyException - 我的异常网
当前位置:我的异常网» C语言 » google笔试题,进来看看,解决方法

google笔试题,进来看看,解决方法(3)

www.MyException.Cn  网友分享于:2013-03-30  浏览:13次

faint..

错了。 。。。。

比如说 :
90 : [?][?] ==> 十位为1, 10种情况。 各位为1, 9种情况。 所以是 19个结果。。
800 : [?][?][?] ==> 10 * 10 + 10 * 8 + 10 * 8 = 260.
7000 : ===> 10 * 10 * 10 + 10 * 10 * 7 + 10 * 10 * 7 + 10 * 10 * 7 = 3100

===================================================

也就是说,如果是针对与 n个9 的或是 1,n个0 的。是我最初的结果。
9, 99,999,9999,...
0,10,100,1000,10000....

如果是n,m个0的。(这里假如首位是n,其中有m个0)
2,3000,4000,500....

================================================
有关系:
f(n,m) = 10^m + m*7*10^(m-1)
================================================真理啊。。。


------解决方案--------------------
本题的关键问题是求f(n)=n的n值列表,故必须对f(n)进行优化,
从题目的定义可知,f(n)函数事实上是求一个BCD码(8421)累加值
并求得每个累加值中1的个数和问题,因此可以将该问题分解为
从1开始的递推累加过程,每个过程分为四个步骤:
(1)求当前值加1后的BCD码(8421)的值。
(2)求当前累加值BCD码中1的个数。
(3)将当前值中1的个数与之前1的个数进行求和。
(4)检查当前n值与累计1的值是否相同,相同则输出n。

由于本题要求是快速准确,而求BCD码的累加值最好的方法是使用
硬件电路,如果使用软件实现,可使用hash真值表的方法。

我在这里采用64K空间的BCD码累加真值表和64K空间的BCD码求1个
数真值表来计算步骤1和步骤2,以达到最佳速度,下面是源代码和
输出结果:
#include "stdafx.h "
#include <windows.h>

int inc1_arr[65536] = {
0X000001,0X000002,0X000003,0X000004,0X000005,0X000006,0X000007,0X000008,0X000009,0X000010,
0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0X000011,0X000012,0X000013,0X000014,
0X000015,0X000016,0X000017,0X000018,0X000019,0X000020,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,
......//数量较多省略(其中下标为0x9999的值为0x010000,值为0xFFFFFF表示BCD码无效)
};

char count1_arr[65536] = {
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
......//数量较多省略
};

int main(int argc, char* argv[])
{
unsigned short usBCD[3] = {0, 0, 0};
int i, k;
int iSum = 0;

DWORD dwTick = GetTickCount();

for(i = 1; i <= 1234567890; i ++) {
k = inc1_arr[usBCD[0]];
usBCD[0] = k & 0xffff;
if(k & 0x00ff0000) {
k = inc1_arr[usBCD[1]];
usBCD[1] = k & 0xffff;
if(k & 0x00ff0000) {
k = inc1_arr[usBCD[2]];
usBCD[2] = k & 0xffff;
}
}
iSum += count1_arr[usBCD[0]] + count1_arr[usBCD[1]] + count1_arr[usBCD[2]];
if(iSum == i) {
printf( "%d\n ", i);
}
}

printf( "\nTime Used: %d mSec\n ", GetTickCount() - dwTick);

return 0;
}

VC++ 6.0下编译通过,在Pentium M 1.4GHz笔记本上的运行结果(不到20秒):
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986

文章评论

10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员和编码员之间的区别
程序员和编码员之间的区别
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
代码女神横空出世
代码女神横空出世
那些争议最大的编程观点
那些争议最大的编程观点
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
每天工作4小时的程序员
每天工作4小时的程序员
一个程序员的时间管理
一个程序员的时间管理
程序员的鄙视链
程序员的鄙视链
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Java程序员必看电影
Java程序员必看电影
总结2014中国互联网十大段子
总结2014中国互联网十大段子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员都该阅读的书
程序员都该阅读的书
我是如何打败拖延症的
我是如何打败拖延症的
如何成为一名黑客
如何成为一名黑客
 程序员的样子
程序员的样子
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
漫画:程序员的工作
漫画:程序员的工作
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
10个调试和排错的小建议
10个调试和排错的小建议
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员必看的十大电影
程序员必看的十大电影
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
老程序员的下场
老程序员的下场
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
鲜为人知的编程真相
鲜为人知的编程真相
旅行,写作,编程
旅行,写作,编程
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有