显示标签为“九章算术”的博文。显示所有博文
显示标签为“九章算术”的博文。显示所有博文

星期日, 九月 21, 2008

九章算术中的分数求平均值(九章算术系列六)

[一五]今有三分之一,三分之二,四分之三。问减多益少,各几何而平?
    答曰:减四分之三者二,三分之二者一,并以益三分之一,而各平于十二分之七。

[一六]又有二分之一,三分之二,四分之三。问减多益少,各几何而平?
    答曰:减三分之二者一,四分之三者四,并以益二分之一,而各平于三十六分之二十三。

平分术曰:母互乘子,副并为平实,母相乘为法。以列数乘未并者各自为列实。亦以列数乘法,以平实减列实,余,约之为所减。并所减以益于少,以法命平实,各得其平。

这部分描述的是分数求平均数的方法,过程是通分求和,然后求分子平均数。

星期六, 八月 30, 2008

九章算术中的分数比较大小(九章算术系列五)

[一二]今有八分之五,二十五分之十六。问孰多?多几何?
    答曰:二十五分之十六多,多二百分之三。

[一三]又有九分之八,七分之六。问孰多?多几何?
    答曰:九分之八多,多六十三分之二。

[一四]又有二十一分之八,五十分之十七。问孰多?多几何?
    答曰:二十一分之八多,多一千五十分之四十三。
    课分术曰:母互乘子,以少减多,余为实,母相乘为法,实如法而一,即相多也。


这部分方法和分数减法相同,只是在最后有一个比较的过程。

辗转相减法求最大公约数要点

辗转相减法在《九章算术》中有所论述

方法如下:
1 用2对分子分母约分,记录约分次数count;
2 如果分子或分母出现奇数,则转到3;
3 分子分母中较大的为a,较小的为b;
4 c = a - b;
5 若c与b不相等,则c与b中较大的为a,较小的为b,回到4;相等则到6;
6 若count为0,则result = c;不为0则c乘以2的count次方的积赋给result;
7 result即为a与b的最大公约数。

这里有一点需要注意:
当a与b相等时,这个算法不能正确处理,所以应保证a与b不相等。但是如果使用辗转相除(欧几里得算法)就没有这个问题。

代码及测试如下:

substraction.c 描述了辗转相减法
====================================================================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//#define _DEBUG_ 1

void print_usage()
{
printf("Usage: rotate_substraction <num1> <num2>");
printf("\n");
}

int rotate_substraction(int num1, int num2, int odd_time)
{
// equal number is itself
if (num1 == num2) {
return num2;
}
#ifdef _DEBUG_
printf("Num1 is : %d\n", num1);
printf("Num2 is : %d\n", num2);
#endif
// half
while (num1 % 2 == 0 && num2 % 2 == 0) {
num1 >>= 1;
num2 >>= 1;
odd_time++;
}

// substrcation
int sub = num1 - num2;
if (sub == num2) {
if (odd_time == 0) {
return sub;
} else {
return sub * pow(2, odd_time);
}
} else {
return rotate_substraction(
sub > num2 ? sub : num2,
sub < num2 ? sub : num2,
odd_time
);
}
}

int main(int argc, char **argv)
{
if (argc < 3) {
print_usage();
return -1;
}

int num1 = atoi(argv[1]);
int num2 = atoi(argv[2]);

printf("[%d, %d]Equal Number is : %d\n", num1, num2,
rotate_substraction(
num1 > num2 ? num1 : num2,
num1 < num2 ? num1 : num2,
0
));

return 0;
}

devision.c 描述了辗转相除法(欧几里得算法)
====================================================================
#include <stdio.h>
#include <stdlib.h>

//#define _DEBUG_ 1

void print_usage()
{
printf("rotate_devision <num1> <num2>");
printf("\n");
}

int rotate_devision(int num1, int num2)
{
#ifdef _DEBUG_
printf("Num1 is : %d\n", num1);
printf("Num2 is : %d\n", num2);
#endif

if (num1 % num2 == 0) {
return num2;
}

int dev = num1 % num2;

return rotate_devision(
dev > num2 ? dev : num2,
dev < num2 ? dev : num2
);
}

int main(int argc, char **argv)
{
if (argc < 3) {
print_usage();
return -1;
}

int num1 = atoi(argv[1]);
int num2 = atoi(argv[2]);

printf("[%d, %d]Equal Number is : %d\n", num1, num2,
rotate_devision(
num1 > num2 ? num1 : num2,
num1 < num2 ? num1 : num2
));

return 0;
}

测试bash脚本
====================================================================
#!/bin/sh

gcc -lm -o substraction substraction.c
gcc -o devision devision.c

for i in $(seq 1 100); do
./substraction 100 $i >> sub_result
./devision 100 $i >> dev_result
diff -i sub_result dev_result > result
cat result
rm *_result
done

我测试了1到10000和10000的最大公约数,两种算法所得结果一致。

九章算术中的分数减法(九章算术系列四)

[一0]今有九分之八,减其五分之一。问余几何?
    答曰:四十五分之三十一。

[一一]又有四分之三,减其三分之一。问余几何?
    答曰:十二分之五。
    减分术曰:母互乘子,以少减多,余为实,母相乘为法,实如法而一。

母互乘子,以少减多,余为实,母相乘为法,实如法而一。

交叉相乘,分子大减小,差为分子,分母相乘做分母

星期五, 八月 29, 2008

九章算术中的分数加法(九章算术系列三)

[七]今有三分之一,五分之二。问合之得几何?
   答曰:十五分之十一。

[八]又有三分之二,七分之四,九分之五。问合之得几何?
   答曰:得一、六十三分之五十。

[九]又有二分之一,三分之二,四分之三,五分之四。问合之得几何?
   答曰:得二、六十分之四十三。
   合分术曰:母互乘子,并以为实,母相乘为法,实如法而一。不满法者,
以法命之。其母同者,直相从之。

母互乘子就是交叉相乘,这里的”实“是分子,”法“是分母。
并以为实,是说乘积作为分子。
母相乘为法,分母相乘作为分母。
实如法而一,用分母除分子,得数为整数部分。
不满法者,以法命之,就是分子比分母小的时候,保留原样。
其母同者,直相从之。 分母相同可以直接运算。

这里有通分的方法,但是没有涉及最小公倍数,而是使用分母直接相乘的更加一般的方法。

星期四, 八月 28, 2008

九章算术中的分数(九章算术系列二)

[五]今有十八分之十二。问约之得几何?

   答曰:三分之二。

[六]又有九十一分之四十九。问约之得几何?
   答曰:十三分之七。
   约分术曰:可半者半之,不可半者,副置分母子之数,以少减多,更相减损,求其等也。以等数约之。


例五说明了可半者半之,就是用2作为约数,化简分数。

例六说明了不可半者这种情况,解题思路在后半部分。


副置分母子之数,以少减多,更相减损,求其等也。以等数约之。

就是用分母和分子为一组,大减小,差和上次较小的数为一组,大减小,如此交替相减,直到得数和减数相同,这个数就是等数,也就是最大公约数。


原理和辗转相除就最大公约数的欧几里得算法在理论上是相通的。


请看贴的同学想两个数求证下我的翻译。


感谢传东和老徐给出的意见。

星期三, 八月 27, 2008

九章算术中的矩形面积计算(九章算术系列一)

locate:九章算术卷一 方田

source:

[一]今有田广十五步,从十六步。问为田几何?
   答曰:一亩。

[二]又有田广十二步,从十四步。问为田几何?
   答曰:一百六十八步。
   方田术曰:广从步数相乘得积步。
   以亩法二百四十步除之,即亩数。百亩为一顷。

[三]今有田广一里,从一里。问为田几何?
   答曰:三顷七十五亩。

[四]又有田广二里,从三里。问为田几何?
   答曰:二十二顷五十亩。
   里田术曰:广从里数相乘得积里。以三百七十五乘之,即亩数。


这里涉及矩形面积、乘法计算、单位换算。