给大家出道题目之二,有趣的小题目(页 1) - C/C++ (STL/boost) - Linux伊甸园论坛

DarkSpy 发表于 2006-9-19 11:33

给大家出道题目之二,有趣的小题目

输入一个数 n, 要求写一个 f( n) 的函数, 计算从 0 到 n 为止有几个 1 出现 v:VkP4G
例如 f(11), 0 ~ 11 就有 4 个 1 出现, 于是就输出 4
0b\)R$d?6@
第二个求出所有 f(n ) == n , 和计算结果一致的数字, 例如我输入 f(1), 那么肯定只有一个 1, 所以 f(n) == n[c(xC([}'V

?wz:qaP}U
1. 不考虑负数情况
2. 不考虑浮点情况
3. 不允许多个参数, 例如 f(n1, n2, ...)

flag 发表于 2006-10-8 09:38

只有一个1的情况比较好判断，超过一个的话还想不出有什么好的算法……

weigern 发表于 2006-10-8 23:26

可以递归来做。

ljj 发表于 2006-10-10 17:48

DS是不是要的这个结果？看看对不对，不对可能是我理解题目错了。这个是我用C＋＋写的，只能是正整数，在BCB用了个界面来显示，如图：a?+Rq0{3w/B

[IMG]http://www5.freep.cn/Photo.aspx?url=PhotoNew_www5/061010/17/0610101744078131.JPG[/IMG]

flag 发表于 2006-10-10 17:51

想法说来看看呢？看图能看明白？

DarkSpy 发表于 2006-10-10 19:34

4 楼的我不太看的明白，但是结果应该是不正确的。

ljj 发表于 2006-10-10 19:38

看不明白？
n=1
f(1)=1@@Pw&J
1的个数 1
n=10 e{:Ul3@V K v;j
f(1)=1 //只有一个数和结果一样!c5K!q!g~
1的个数　2
n=11_kk5D@@D D
f(1)=1 //也只有一个数和结果一样4I)y$A}!y|0x
1的个数　4

下面同样.;F&hr&l m5oI/V

我只是把要判断的数换成字符判断，如果是1就count＋＋，if(count==n)　时输出　f(n)==n来，然后再进行下一个数的判断。+`{Fw/?
+wjl C2{,Wfz8e]L
完了。

DarkSpy 发表于 2006-10-10 19:39

提示一下，这道题目应该将算法拆开看，递归是一个办法，但是算法拆开能提高很多的速度。当然暴力法也是可以，但是速度就不行了。

ljj 发表于 2006-10-10 19:43

看来我还是没弄懂题目，能不能再详细点？

海天一色 发表于 2006-10-12 10:49

第一个问题$_u E+X3g
可以先把n（可以表示成abcde这样的格式）拆成 e+d0+c00+b000+a0000这样的数之和
再分别统计在个、十、百、千等位上（分别与10、100、1000、10000取余结果为e、d、c、b）出现的1的个数之和。}6mI'u)cW
最后再统计最高位（a）为1--a时出现的1的个数。
再算整十、整百、整千等可以利用递归算法。

DarkSpy 发表于 2006-10-15 13:09

[QUOTE=ljj]看来我还是没弄懂题目，能不能再详细点？[/QUOTE]X3bkGS A.Tu
?7P&S1J5z3?Eo E#?
输入一个数 n, 要求写一个 f( n) 的函数, 计算从 0 到 n 为止有几个 1 出现，函数返回出现 1 的数字的值。duE(e8mQ&K-UJ
例如 f(11), 0 ~ 11 就有 4 个 1 出现, 于是就返回 4
/Un8Md7FNH-^rj
第二个是在第一道题目的算法基础上，求出所有 f(n ) == n , 和计算结果一致的数字, 例如我输入 f(1), 那么肯定只有一个 1, 所以 f(n) 返回的是 1，而n 也是 1，那么 f(n)肯定是 == n 了。

4l8u G(rs ZNWjF
1. 不考虑负数情况 Lg(`BQ V6c
2. 不考虑浮点情况
3. 不允许多个参数, 例如 f(n1, n2, ...)

willing 发表于 2006-10-17 15:14

应该比较简单吧。

ljj 发表于 2006-10-17 15:51

[QUOTE=DarkSpy]输入一个数 n, 要求写一个 f( n) 的函数, 计算从 0 到 n 为止有几个 1 出现，函数返回出现 1 的数字的值。hl NWSE^J
例如 f(11), 0 ~ 11 就有 4 个 1 出现, 于是就返回 4[/QUOTE]ba+H1m8W%ms

我觉得我的结果没有错啊。

iTK7L)u~
f(n): 输出 1 的个数：q(qxYa_/a
f(1)  输出 1；f(10)　输出 2　；f(11) 输出 4　；f(11110)输出 5555　；
f(199981) 输出 199981 ;  f(200001) 输出 200001

[QUOTE=DarkSpy]第二个是在第一道题目的算法基础上，求出所有 f(n ) == n , 和计算结果一致的数字, 例如我输入 f(1), 那么肯定只有一个 1, 所以 f(n) 返回的是 1，而n 也是 1，那么 f(n)肯定是 == n 了。[/QUOTE]O-J)D J&PQ8_

f(1)  输出 1:这时 f(1)=1;
f(199981) 输出 199981 ;　这里有两个结果(1 的个数 )和输入的数字相等f(1)==1; f(199981)==199981 (1 的个数和输入的数字相等).uku%Llx-U[*M
同样：
f(200001) 输出 200001 ;这里有十二个结果(1 的个数 )和输入的数字相等　f(1)==1; f(199981)==199981 ; f(199982)==199982 ; f(199983)==199983 ; f(199984)==199984 ; f(199985)==199985 ; f(199986)==199986 ; f(199987)==199987 ; f(199988)==199988 ;    f(199989)==199989 ;......f(200001)==200001 (1 的个数和输入的数字相等)P(EJP3W c)w

由此我认为在 n<199981 中，只有一个结果和输入的数（n）相等，就是 n=1 的时候。

DarkSpy 发表于 2006-10-18 08:23

嗯,结果是对的,你的截图我没看清楚.WJ"_#K6ar'}/gD
下面你可以给出你的算法.6xZn:W-JR
我女朋友也是程序员,她的算法速度巨快,令人感慨.:-D

flag 发表于 2006-10-18 09:49

[QUOTE=DarkSpy]我女朋友也是程序员,她的算法速度巨快,令人感慨.:-D[/QUOTE]V0o P!Q B;x0G
那可要仰视一下了，不过DarkSpy上次的给答案了吗？不厚道呦 :w

DarkSpy 发表于 2006-10-18 10:53

其实这道题目和上次的比,如果需要优化的话, 两道都有稍许难度,如果普通做的话, 是无所谓难度的,*BcOv)mgomW2n3M
两道题目都可以用暴力法做.,K3liLY*g1}
第一道其实是类似背包问题,应该是NP的,

ljj 发表于 2006-10-18 15:23

[QUOTE=DarkSpy]嗯,结果是对的,你的截图我没看清楚.
下面你可以给出你的算法. i.KT:s7U6aB
我女朋友也是程序员,她的算法速度巨快,令人感慨.:-D[/QUOTE]6Xs9t1ecK
&g8?|R7O
:) 没什么算法可言，我只是把要判断的数换成字符判断，如果是1就count＋＋，if(count==n)　时输出　f(n)==n来，然后再进行下一个数的判断。b!A:a!W5T8g
SxX!Svt6dJg
完了。
/S'`-WY M"N,HUP
vQqone'TxVWR
可能运行起来比较慢，我输入999999　时，在　CPU：C1.7　内存：512M　大约用了15秒。　

DarkSpy 发表于 2006-10-18 16:21

那你应该用的暴力法了

页: [1]

Linux伊甸园论坛's Archiver

给大家出道题目之二,有趣的小题目