一道算法题，怎么也想不出来怎么把结果算成标准答案

[Q Zhongyu]

/* 半径为r的黒圆，里面有个半径r/2的白圆，白圆里又有一个半径为r/4的黒圆，

此黒圆里又有一个半径为r/8的白圆入错重复下去，问黑色部分的面积为多少？

*******************************************************************************************

标准答案输入 2 输出 4pi 下面是我的算法

*/

# include <stdio.h>

int sm(int ds,int sum,int flag);

int main(){

int r;

printf("请输入圆的半径：");

scanf("%d",&r);

printf("%d\n",r);

printf("%dpi\n",sm(r,r*r,-1));

return 0;

}

int sm(int ds,int sum,int flag){

if (ds == 0)

return sum;

else

printf("递归中的sum=%d\n",sum);

return sm(ds / 2,sum + (ds / 2) * (ds / 2) * flag,flag*(-1));

}

[Robber Phex]

你的算法怎么觉得是无穷递归的？ds一直除以2啊。
但是你使用了int型，这样以来就不符合题意了。

这种问题还是永数学方法解吧。

2013/6/17 Q Zhongyu <snows...@gmail.com>

--
-- You received this message because you are subscribed to the Google Groups Shanghai Linux User Group group. To post to this group, send email to sh...@googlegroups.com. To unsubscribe from this group, send email to shlug+un...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/shlug?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Shanghai Linux User Group”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

--
Regards,
RobberPhex

About me: http://about.me/RobberPhex

[Q Zhongyu]

对啊！我吧ds的类型改成double也不行，出来的还是一对莫名其妙的答案，所以改回int类型了，这个递归当ds==0的时候就有出口了，但是貌似怎么也达到不到0。

所以感觉根本思路就是错的，所以来求思路，如果能把这个代码改出来那就更好了

在 2013年6月17日星期一UTC+8下午1时48分05秒，Robber Phex写道：

[Robber Phex]

我算出来的结果是4*(pi)*r*r/5。

微积分，无穷级数求和。

2013/6/17 Q Zhongyu <snows...@gmail.com>

[none_nobody]

浮点不能比较0，

要比较 小于某个值，比如0.0000000001 ，后面算面积乘方就没有了。

还有，你那个flag = flag *  (-1)

没说减去白色部分面积啊。

[Chaos Eternal]

减了。

但是他不应该写(ds/2)

2013/6/17 none_nobody <lyx...@gmail.com>:

[Q Zhongyu]

求指教，该怎么写呢？

在 2013年6月17日星期一UTC+8下午2时17分17秒，Soahc Lanrete写道：

[Yiling Cao]

算法错 ＋ int错

int 算个毛啊？你知道float 和int 的区别吗？

而且你想用是用monte carlo simulation 做还是用数学极限／积分做？

2013/6/17 Q Zhongyu <snows...@gmail.com>

[Huang Hang]

Monte Carlo不是很好吧，

首先可以假定这些圆在同一点内切

然后要判断一个随机点是在白色或黑色圆内，

离相切点较远的点还比较容易判断是黑是白，但落到相切点附近的点就可能要追溯到很深层嵌套的圆才能确定黑白。

2013/6/17 Yiling Cao <yilin...@gmail.com>

--
Best regards, 
Huang Hang

[Chaos Eternal]

可以考虑射影到一个对数坐标上嘛。


2013/6/17 Huang Hang <seak...@gmail.com>:

[Q Zhongyu]

用极限写的

在 2013年6月17日星期一UTC+8下午3时06分47秒，c2h2写道：

[尹川]

>我算出来的结果是4*(pi)*r*r/5

我也觉得结果是3.2pi

我是计算黑色圆环的面积，然后 r/4 递归累加，当r足够小时结束递归。

用Python写的，不知道对不对

radius = 2.0

def area(r):

if r < 0.0000000001:

return 0

else:

return 0.75 * r * r + area(r/4) 

print area(radius)

2013/6/17 Q Zhongyu <snows...@gmail.com>

--

一片树林里分出两条路——
        而我选择了人迹更少的一条，
        从此决定了我一生的道路。

Site: www.chuan-small.me

[Huang Hang]

转换坐标系的话，会不会反过来增加扔随机点的难度？

毕竟我们考察的面积是通常的Cartesian坐标系的面积，转换成对数坐标的话会不会导致面积比例很难换算？不懂解析几何，求相关资料链接

2013/6/17 Chaos Eternal <chaose...@shlug.org>

[Q Zhongyu]

好吧 老衲根据网友们的提示写出来了

# include <stdio.h>

float sm(float ds, float res, int flag) {

if (ds < 0.00001) 

return res;

return sm(ds/2.0, res + ds*ds*flag, flag*-1);

}

int main()

{

float r;

scanf("%f",&r);

printf("%f\n", sm(2, 0, 1));

}

答案貌似是错误的，结果确实是3.2 感谢大家的帮助

您收到此邮件是因为您订阅了 Google 网上论坛“Shanghai Linux User Group”中的主题。
要退订此主题，请访问 https://groups.google.com/d/topic/shlug/uKF-GeWzV1Y/unsubscribe。
要退订此论坛及其所有主题，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

[none_nobody]

你为什么scanf 了一个 r, 而又不用呢？

[none_nobody]

还有，就是你漏了一 pi 哈。圆的面积，不是正方形。

On Monday, June 17, 2013 10:15:36 PM UTC+8, none_nobody wrote:

你为什么scanf 了一个 r, 而又不用呢？

[Q Zhongyu]

不好意思忘记了

[Chaos Eternal]

这个简单，每个点再按离原点的距离远近用对数加权就可以了嘛。

2013/6/17 Huang Hang <seak...@gmail.com>:

[david pu]

这个不是传说中小时候学的等比数列求和么？公比 |q| < 1 Sn = a1/(1-q)

2013/6/17 Chaos Eternal <chaose...@shlug.org>

--
 ()   ASCII Ribbon Campaign
 /\   Keep it simple!

[Q Zhongyu]

你怎么想到的！真厉害啊

您收到此邮件是因为您订阅了 Google 网上论坛“Shanghai Linux User Group”中的主题。
要退订此主题，请访问 https://groups.google.com/d/topic/shlug/uKF-GeWzV1Y/unsubscribe。

要退订此论坛及其所有主题，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

[david pu]

你们说的太高深了我都不懂，我只是用土办法研究了一下。

2013/6/18 Q Zhongyu <snows...@gmail.com>

[Yu Changyuan]

实在无力吐槽了。。。

算法的最高境界不就是直接手算出公式（最终结果），然后然计算机代入一下吗？

[Chaos Eternal]

麻烦楼上手算一下exp(2, exp(2,65536)+1)+1是否是素数? 然后告诉你面前的计算机

2013/6/18 Yu Changyuan <rei...@gmail.com>:

[Q Zhongyu]

递归就是给计算机解决的问题，大神你就别为难楼上了

[Yu Changyuan]

不是质数。

假如2^n+1能被3整除，
那么，4*2^n+4也能被3整除，
所以2^(n+2)+1能被3整除，
又因为2^1+1能被3整除，
所以2的奇数次方+1都能被3整除。

2^65536+1是奇数，
所以2^(2^65536+1)+1能被3整除，
故不是质数。

[Chaos Eternal]

算了，计算机只要取代除了你以外的人就可以了。至于你，等你自然老死之后，也就没事了。

2013/6/18 Yu Changyuan <rei...@gmail.com>:

[依云]

On Tue, Jun 18, 2013 at 06:30:32AM -0700, Zang MingJie wrote:
> 对于小学数学不及格到人，wolframalpha是你到好伙伴
>
> http://www.wolframalpha.com/input/?i=sum+pi+*+%28-1%2F4%29%5Ex+*+r%5E2+x+from+0+to+inf

这个怎么笔算呢？哪位小学数学及格了的来讲解下？

--
Best regards,
lilydjwg

Linux Vim Python 我的博客:
http://lilydjwg.is-programmer.com/
--
A: Because it obfuscates the reading.
Q: Why is top posting so bad?

[Yu Changyuan]

我小学及格了，自认为学的不错，所以说一下具体的计算过程。
需要声明的是，等比数列求（特别是|q| < 1的无穷数列）和应该是中学的内容，对于小学生来说，属于超纲的（如果你是搞奥数的，当我没说），但是其他知识点确实是小学学的。

首先，通过观察，可以知道，黑色的总面积是由一系列不重叠的黑环相加而成。
然后，每个小一号的黑环是外面黑环的面积的1/16（因为内径、外径均为前一个环的1/4）。
再次，最大的黑环的面积是pi*r*r - pi * (r/2) * (r/2) = 3/4 pi * r * r
最后，所有的黑环的面积是以3/4 pi * r * r为初项，q=1/16为公比的等比数列的和，即 3/4*pi*r*r * 1 / (1-q) = 4/5*pi*r*r

另外一种思路：
黑的面积是第一个黑圆的面积减第一个白圆的面积再加第二个黑圆的面积再减第二个白圆的面积...
即初项为 pi*r*r，公比为-1/4的等比数列的和，也就是 pi*r*r*1/(1-(-1/4)) = 4/5*pi*r*r。

--
-- You received this message because you are subscribed to the Google Groups Shanghai Linux User Group group. To post to this group, send email to sh...@googlegroups.com. To unsubscribe from this group, send email to shlug+un...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/shlug?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Shanghai Linux User Group”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。

--
Best regards,
Changyuan

[Chaos Eternal]

小学除了不需要证明级数必收敛，其实还是有这个题的

2013/6/21 Yu Changyuan <rei...@gmail.com>:

[Chaos Eternal]

因为等比级数求和很简单 : sigma (a^n)=a+a*(sigma(a^n))
所以 sigma(a^n)=a/(1-a)

但是如果a>=1 这个级数就发散了啊。。。

2013/6/21 Chaos Eternal <chaose...@shlug.org>:

[依云]

On Fri, Jun 21, 2013 at 11:02:23PM +0800, Chaos Eternal wrote:
> 因为等比级数求和很简单 : sigma (a^n)=a+a*(sigma(a^n))
> 所以 sigma(a^n)=a/(1-a)
>
> 但是如果a>=1 这个级数就发散了啊。。。

原来是级数么……请原谅我只看了公式没看题……

[Yu Changyuan]

这让我想起了 1-1+1-1+1-1 ... 等于1/2的计算过程。

2013/6/21 Chaos Eternal <chaose...@shlug.org>

--
Best regards,
Changyuan

[Chaos Eternal]

这个级数不是可以等于任何值么。。。

2013/6/21 Yu Changyuan <rei...@gmail.com>:

[Qian Hong]

2013/6/22 Chaos Eternal <chaose...@shlug.org>:
> 这个级数不是可以等于任何值么。。。

条件收敛级数经过重排可以收敛为任何实数，这个1+1-1+1 。。。 的级数按通常的定义来说是发散的而不是条件收敛的，没办法“等于任何值”

这里是上海数学用户组么？


--
Regards,
Qian Hong

-
http://www.winehq.org

[Chaos Eternal]

我说的是用我上面给出的那个“技巧”来算出级数的和，而不是真正的等于。
也就是说，如果用我前面一封邮件的技巧的话， 1+1-1+1..这个级数不光可以算出1/2, 还可以算出任何值来。

另外，这里是上海小学生数学竞赛用户组，要求不要太高。


2013/6/22 Qian Hong <frac...@gmail.com>:

[Qian Hong]

2013/6/22 Chaos Eternal <chaose...@shlug.org>:

> 我说的是用我上面给出的那个“技巧”来算出级数的和，而不是真正的等于。
> 也就是说，如果用我前面一封邮件的技巧的话， 1+1-1+1..这个级数不光可以算出1/2, 还可以算出任何值来。
>
> 另外，这里是上海小学生数学竞赛用户组，要求不要太高。

惨了，对自己的幽默感真捉急。

[Wang King]

（1+1/(4^2) + 1/(16^2) + 1/(64^2) + ....) * 3/4 * pi * r^2

这种r限制应该是正确的。

在 2013年6月17日星期一UTC+8下午6时23分25秒，尹川写道：

>我算出来的结果是4*(pi)*r*r/5

我也觉得结果是3.2pi

我是计算黑色圆环的面积，然后 r/4 递归累加，当r足够小时结束递归。

用Python写的，不知道对不对

radius = 2.0

def area(r):

if r < 0.0000000001:

return 0

else:

return 0.75 * r * r + area(r/4) 

print area(radius)

2013/6/17 Q Zhongyu <snows...@gmail.com>

用极限写的

在 2013年6月17日星期一UTC+8下午3时06分47秒，c2h2写道：

算法错 ＋ int错

int 算个毛啊？你知道float 和int 的区别吗？

而且你想用是用monte carlo simulation 做还是用数学极限／积分做？

2013/6/17 Q Zhongyu <snows...@gmail.com>

求指教，该怎么写呢？

在 2013年6月17日星期一UTC+8下午2时17分17秒，Soahc Lanrete写道：

减了。

但是他不应该写(ds/2)

2013/6/17 none_nobody <lyx...@gmail.com>:

> 浮点不能比较0，
>
> 要比较 小于某个值，比如0.0000000001 ，后面算面积乘方就没有了。
>
> 还有，你那个flag = flag *  (-1)
>
> 没说减去白色部分面积啊。
>
>
>
>
> On Monday, June 17, 2013 1:53:02 PM UTC+8, Q Zhongyu wrote:
>>
>>
>> 对啊！我吧ds的类型改成double也不行，出来的还是一对莫名其妙的答案，所以改回int类型了，这个递归当ds==0的时候就有出口了，但是貌似怎么也达到不到0。
>>

> --
> -- You received this message because you are subscribed to the Google Groups
> Shanghai Linux User Group group. To post to this group, send email to

> sh...@googlegroups.com. To unsubscribe from this group, send email to
> shlug+un...@googlegroups.com. For more options, visit this group at

> https://groups.google.com/d/forum/shlug?hl=zh-CN
> ---
> 您收到此邮件是因为您订阅了 Google 网上论坛的“Shanghai Linux User Group”论坛。

> 要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 shlug+un...@googlegroups.com。
> 要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
>
>

--
-- You received this message because you are subscribed to the Google Groups Shanghai Linux User Group group. To post to this group, send email to sh...@googlegroups.com. To unsubscribe from this group, send email to shlug+un...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/shlug?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Shanghai Linux User Group”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

--
-- You received this message because you are subscribed to the Google Groups Shanghai Linux User Group group. To post to this group, send email to sh...@googlegroups.com. To unsubscribe from this group, send email to shlug+un...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/shlug?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Shanghai Linux User Group”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 shlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

--

一片树林里分出两条路——
        而我选择了人迹更少的一条，
        从此决定了我一生的道路。

Site: www.chuan-small.me

[Wang King]

可以用递归， 但是参数类型有问题

半径应该用double型， 而且应该用ds < 0.000001(某个double型值， 不要超出double所能表达的精度）作为退出条件

以下是你程序执行的ds变化过程， 可以debug一下看看， 两论之后递归将结束

1、ds=2， ds/2 = 1

2、ds =1， ds/2 = 0.5， ds = 0。 结束

在 2013年6月17日星期一UTC+8下午1时37分45秒，Q Zhongyu写道：

/* 半径为r的黒圆，里面有个半径r/2的白圆，白圆里又有一个半径为r/4的黒圆，

此黒圆里又有一个半径为r/8的白圆入错重复下去，问黑色部分的面积为多少？

*******************************************************************************************

标准答案输入 2 输出 4pi 下面是我的算法

*/

# include <stdio.h>

int sm(int ds,int sum,int flag);

int main(){

int r;

printf("请输入圆的半径：");

scanf("%d",&r);

printf("%d\n",r);

printf("%dpi\n",sm(r,r*r,-1));

return 0;

}

int sm(int ds,int sum,int flag){

if (ds == 0)

return sum;

else

printf("递归中的sum=%d\n",sum);

return sm(ds / 2,sum + (ds / 2) * (ds / 2) * flag,flag*(-1));

}