中文中有三个发“ta“音的人称代词,一个是”他“代表男性,一个是”她“代表女性,一个是”它“代表除了人以外的事物。英文中对应he,she和it。
在许多校内应用中,这些都被“TA”这个拼音形式的词所代替,减少了程序的判断分支,提高了运行速度,而且在表现形式上更加俏皮,深受用户喜爱。
星期六, 八月 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的最大公约数,两种算法所得结果一致。
方法如下:
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作为约数,化简分数。
例六说明了不可半者这种情况,解题思路在后半部分。
副置分母子之数,以少减多,更相减损,求其等也。以等数约之。
就是用分母和分子为一组,大减小,差和上次较小的数为一组,大减小,如此交替相减,直到得数和减数相同,这个数就是等数,也就是最大公约数。
原理和辗转相除就最大公约数的欧几里得算法在理论上是相通的。
请看贴的同学想两个数求证下我的翻译。
订阅:
博文 (Atom)
