分类目录归档:C/C++

绘制整系数多项式复数根的分布

我在百度贴吧Mathematica吧的这个帖子看到有人在研究如下问题:

求解所有系数为1或-1的n次多项式的根,然后把所有这样的根绘制到复平面上。

我想起以前在Matrix67的博客上也看到过这个问题,里面介绍了Sam Derbyshire用Mathematica跑了四天四夜(也有说法是三天三夜)生成了n=24的所有根,然后用Java程序绘图,得到了下图:

roots1

贴吧中的“三分钟复现”是算到n=17的情况。由于n增加1导致需要求解方程的数量翻倍,每个方程中根的个数也增加1,所以我估计了一下,n=24时大约需要求出24*2^24=402M个解。(24次多项式包括常数项有25个系数,但是由于对称性可以省去一半计算。)这些计算显然不需要以天为数量级的时间。

我决定用C语言解决这个问题,同时改善一下显示的效果,并尝试绘制分辨率更高的图。

解决这个问题有两个比较麻烦的事:

  • 如何求解多项式的根
  • 图上的颜色按照什么绘制

继续阅读绘制整系数多项式复数根的分布

C++的直接初始化与复制初始化

C++中的直接初始化指的是直接调用类的构造函数进行初始化,例如

复制初始化指的是用“=”号来初始化对象,例如

在上面的例子中,这两种写法是完全等效的,但是直接初始化和复制初始化在一些情况下还是有区别的。

继续阅读C++的直接初始化与复制初始化

为什么C++直接输出21000可以精确到个位

这个想法源于一道程序设计课的上机题:任意给定一个正整数N(N< =100),计算2的n次方的值。 这道题的本意是练习高精度计算,但是可以发现,使用long double类型调用pow函数就足够了。当然我还是用高精度计算写的。 然而,我发现即使仅使用double,甚至用float,在C++中都可以输出正确的答案。 运行下面的C++代码:

输入1000,程序输出一个超过300位的结果,虽然这早已超出double和long double的精度,但是运算结果是完全正确的。 至于结果的正确性,比较方便的方法就是与Python给出的结果进行对比。在Python的控制台中输入2**1000可以直接得到高精度计算的结果,很方便。 为什么结果是精确的呢? 继续阅读为什么C++直接输出21000可以精确到个位

C/C++中的const可信吗?

C和C++中有很多函数的参数类型使用了const这个关键字。例如C语言string.h头文件中的strcpy字符串复制函数,它的原型是

其中的const表示strcpy函数保证不修改Source指向的内存中的数据,而未加const的Dest指向的内容却可以被修改。

再如stdlib.h中的qsort快速排序函数原型如下:

其中最后一个参数是一个函数指针,qsort需要你提供一个比较函数,这个比较函数以两个指针为参数,const要求你不能通过指针修改其指向的数据。

然而指针类型的参数加了const的函数就真的能保证它不会修改数据吗?

继续阅读C/C++中的const可信吗?

【π Day】一段很短的计算圆周率的代码

今天是3月14日,圆周率日。

我在网上看到了一段很短的计算圆周率的代码,可以算到8000位。我把程序输出的结果和Mathematica的结果比较了一下,验证了程序是正确的。

通过更改c的值和f数组的大小,可以算到更多的位。

我没弄明白这段代码的原理,如果有谁知道,欢迎在回复中告诉我。

简短版:

正常版:
继续阅读【π Day】一段很短的计算圆周率的代码

只用位运算来写整数四则运算程序

整数在计算机中是以二进制形式存储的,整数的运算归根到底是二进制位的逻辑运算。

那么如何用最基本的位运算来实现整数的四则运算?

我今天写了“加”、“减”、“乘”、“除”、“取余”和“取相反数”这几种基本运算,代码中只用到了位运算。

我选择的是short型数值,并用代码循环了所有可能的情况(两个操作数分别从-32768到32767),可以验证我的运算函数的结果和直接做运算的结果是完全相同的(包括溢出的情况)。这些函数经过简单修改很容易支持更多位的整数。

有符号整数右移操作会复制符号位,我把一些函数的参数设置成了unsigned类型的,但是调用函数的时候可以直接传进有符号数。“加”、“减”、“乘”函数传进无符号数也可以得到正确结果。

由于有符号数中负数比正数多一个-32768,所以为了让程序支持边界条件,除法运算中所有操作都是针对负数进行的。

下面附代码:

继续阅读只用位运算来写整数四则运算程序

scanf函数中的扫描集

ANSI C语言标准向scanf函数增加了一种新特性,叫做扫描集。利用此特性可以解决一些处理文本时的棘手问题。

最开始源于我对CSV(逗号分隔值)文件的处理。(本文不考虑CSV文件中引号和转义字符等其他特性)

例如下面这段代码

如果用它读入下面的数据:

Alice,Bob

会直接把“Alice,Bob”赋值给a而继续等待输入b。

我在网上查了这种问题的解决方法,较为简便的一种就是利用扫描集。

继续阅读scanf函数中的扫描集