#include
void main()
{
int i,z,x,y,j;
printf("please input z:");//输入整数
scanf("%d",&z); for(i=1;i<=z;i++)//i:整数序列的个数for(x=1;x<=z;x++)
{
y=i-1+x;
if((y+x)*i==2*z)
{
for(j=x;j<=y;j++)
printf("%3d",j);
printf("\n");
}
}
}
《数据结构实验》指导书Data Structures and Algorithms Laboratory Projects 王金荣 2014-09-11
目录 1《数据结构实验》课程实验教学大纲--------------------------------------1 2 实验准备: 如何使用VC 6.0? ----------------------------------------------3 3 Projects---------------------------------------------------------------------------8 3.1 Project 1: 算法性能测量-------------------------------------------------8 3.2 Project 2: 有序表归并实验---------------------------------------------10 3.3 Project 3: 数据转换------------------------------------------------------11 3. 4 Project 4: 二叉树遍历实验---------------------------------------------12 3. 5 Project 5-1: 堆排序算法实现------------------------------------------13 3. 6 Project 5-2: 归并排序算法实现---------------------------------------14 3. 7 Project 5-3: 快速排序算法实现---------------------------------------15 3. 8 Project 6-1: 图的深度优先搜索---------------------------------------16 3. 9 Project 6-2 : 图的广度优先搜索---------------------------------------17 3.10 Project 7: 散列实验---------------------------------------------------18 4.1 ACM题目-------------------------------------------------------------------19 4.1 ACM 1: ACboy needs your help again!-------------------------------19 4.2 ACM 2: Jumping the Queue--------------------------------------------21 4.3 ACM 3: Median ----------------------------------------------------------23 4.4 ACM 4: Ignatius and the Princess I------------------------------------25 5 实验报告格式-----------------------------------------------------------------28 6实验报告上交说明-----------------------------------------------------------29
连续自然数立方和的公式 “图形法“ 早在公元100年前后,毕达哥拉斯学派的继承人尼科马霍斯,在他的著作《算术入门》中就曾经用非 常简单的方法推导过这个公式。 奇数列1,3,5,7,9,11,13,…有一个性质,很容易验证: 请你自上而下仔细观察这一系列等式的左端: 第1个等式左端,结束于第1个奇数; 第2个等式左端,结束于第3个奇数; 第3个等式左端,结束于第6个奇数; 第4个等式左端,结束于第10个奇数; 第5个等式左端,结束于第15个奇数; …… 结果发现,这些奇数的序数1,3,6,10,15,…原来是“三角形数”,它的每一项等于从1开始的连 续自然数的和。第1项是1,第2项是1+2=3,第3项是1+2+3=6,第4项是1+2+3+4=10,第5 项是1+2+3+4+5=15,……第n项是1+2+3+…+n=n(n+1)/2。即,第n个等式左端,结束于第n(n +1)/2个奇数。 然后,对上面这一系列等式的左右两端,分别求和: 右端是连续自然数的立方和13+23+33+…+n3。 左端是连续奇数的和。我们知道,求连续奇数的和,求到第几个奇数,就等于第几个奇数的平方。现在,求到第n(n+1)/2个奇数,当然等于[n(n+1)/2]2。 这样就得到求连续自然数立方和的公式: 这种方法思路清晰论证简单。尼科马霍斯之所以能够想到这个方法,显然跟毕达哥拉斯学派对图形数的 宠爱有关。图形数是自然数的形象化,自然数是众数之源,自然数真是一个取之不尽用之不竭的宝藏。
“列表法” 这里再介绍一种列表法,同样可以推出这个公式,并且更简单,更好理解。 第一步:列一个表,在第一行填入一个因数1、2、3、4、5,在第一列填入另一个因数1、2、3、4、5。 第二步:在右下方的空格里分别填入对应的两个因数的积。 显然,所有乘积的和等于 这5块依次是:
自然数平方与立方数列前n 项和公式证明 huangjianwxyx 以下公式,尤其是二、三公式的推导体现了递推消项数学思想。 一、证明:Sn=∑=n k k 1=1+2+3+…+n =(1+n)n/2 证:(略) 二、证明:Sn=∑=n k k 12=12+22+32+…+n2= [n(n +1)(2n +1)]/6 证: (n +1)3-n3=(n3+3n2+3n +1)-n3=3n2+3n +1,则: 23-13=3×12+3×1+1(n 从1开始) 33-23=3×22+3×2+1 43-33=3×32+3×3+1 53-43=3×42+3×4+1 63-53=3×52+3×5+1 … (n +1)3-n3=3×n2+3×n +1(至n 结束) 上面左右所有的式子分别相加,得: (n +1)3-13=3×[12+22+32+…+n2]+3×[1+2+3+…+n]+n ∴ (n +1)3-1=3Sn +3×[n(n +1)/2]+n ∴Sn=12+22+32+…+n2= [n(n +1)(2n +1)]/6 三、证明:Sn=∑=n k k 13=13+23+.....+n 3=n 2(n+1)2/4=[n(n+1)/2] 2 证: (n+1) 4-n 4=[(n+1)2+n 2][(n+1)2-n 2]=(2n 2+2n+1)(2n+1)=4n 3+6n 2+4n+1则: 24-14=4*13+6*12+4*1+1 (n 从1开始) 34-24=4*23+6*22+4*2+1 44-34=4*33+6*32+4*3+1 ... (n+1) 4-n 4=4*n 3+6*n 2+4*n+1(至n 结束) 上面左右所有的式子分别相加,得: (n+1) 4-1=4*(13+23+.....+n 3)+6*(12+22+32+…+n2)+4*(1+2+3+...+n)+n ∴4*(13+23+.....+n 3)= (n+1) 4-1+6*[n(n+1)(2n+1)/6]+4*[(1+n)n/2]+n =[n(n+1)]2 ∴Sn=13+23+.....+n 3=[n(n+1)/2] 2
整式的运算法则 整式的加减法:(1)去括号;(2)合并同类项。 整式的乘法:),(都是正整数n m a a a n m n m +=? ),(都是正整数)(n m a a mn n m = )()(都是正整数n b a ab n n n = 2 2))((b a b a b a -=-+ 2 222)(b ab a b a ++=+ 2 222)(b ab a b a +-=- 整式的除法:)0,,(≠=÷-a n m a a a n m n m 都是正整数 【注意】(1)单项式乘单项式的结果仍然是单项式。 (2)单项式与多项式相乘,结果是一个多项式,其项数与因式中多项式的项数 相同。 (3)计算时要注意符号问题,多项式的每一项都包括它前面的符号,同时还要 注意单项式的符号。 (4)多项式与多项式相乘的展开式中,有同类项的要合并同类项。 (5)公式中的字母可以表示数,也可以表示单项式或多项式。 (6) ),0(1 );0(10为正整数p a a a a a p p ≠= ≠=- (7)多项式除以单项式,先把这个多项式的每一项除以这个单项式,再把所得 的商相加,单项式除以多项式是不能这么计算的。 一、选择(每题2分,共24分)
1.下列计算正确的是(). A.2x2·3x3=6x3B.2x2+3x3=5x5 C.(-3x2)·(-3x2)=9x5D.5 4 x n· 2 5 x m= 1 2 x m+n 2.一个多项式加上3y2-2y-5得到多项式5y3-4y-6,则原来的多项式为().A.5y3+3y2+2y-1 B.5y3-3y2-2y-6 C.5y3+3y2-2y-1 D.5y3-3y2-2y-1 3.下列运算正确的是(). A.a2·a3=a5B.(a2)3=a5C.a6÷a2=a3D.a6-a2=a4 4.下列运算中正确的是(). A.1 2 a+ 1 3 a= 1 5 a B.3a2+2a3=5a5C.3x2y+4yx2=7 D.-mn+mn=0 二、填空(每题2分,共28分) 6.-xy2的系数是______,次数是_______. 8.x_______=x n+1;(m+n)(______)=n2-m2;(a2)3·(a3)2=______. 9.月球距离地球约为3.84×105千米,一架飞机速度为8×102千米/时,?若坐飞机飞行这么远的距离需_________. 10.a2+b2+________=(a+b)2a2+b2+_______=(a-b)2 (a-b)2+______=(a+b)2 11.若x2-3x+a是完全平方式,则a=_______. 12.多项式5x2-7x-3是____次_______项式. 三、计算(每题3分,共24分)
第二节 整数的性质及其应用(1) 基础知识 整数的性质有很多,这里我们着重讨论整数的整除性、整数的奇偶性,质数与合数、完 全平方数及整数的尾数等几个方面的应用。 1.整除的概念及其性质 在高中数学竞赛中如果不加特殊说明,我们所涉及的数都是整数,所采用的字母也表示整数。 定义:设b a ,是给定的数,0≠b ,若存在整数c ,使得bc a =则称b 整除a ,记作a b |, 并称b 是a 的一个约数(因子),称a 是b 的一个倍数,如果不存在上述c ,则称b 不能整除a 记作b a 。 由整除的定义,容易推出以下性质: (1)若c b |且a c |,则a b |(传递性质); (2)若a b |且c b |,则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。若 反复运用这一性质,易知a b |及c b |,则对于任意的整数v u ,有)(|cv au b ±。更一般,若 n a a a ,,,21 都是b 的倍数,则)(|21n a a a b +++ 。或着i b a |,则∑=n i i i b c a 1|其中 n i Z c i ,,2,1, =∈; (3)若a b |,则或者0=a ,或者||||b a ≥,因此若a b |且b a |,则b a ±=; (4)b a ,互质,若c b c a |,|,则c ab |; (5)p 是质数,若n a a a p 21|,则p 能整除n a a a ,,,21 中的某一个;特别地,若p 是 质数,若n a p |,则a p |; (6)(带余除法)设b a ,为整数,0>b ,则存在整数q 和r ,使得r bq a +=,其中b r <≤0,并且q 和r 由上述条件唯一确定;整数q 被称为a 被b 除得的(不完全)商,数r 称为a 被b 除得的余数。注意:r 共有b 种可能的取值:0,1,……,1-b 。若0=r ,即为 a 被 b 整除的情形; 易知,带余除法中的商实际上为??????b a (不超过b a 的最大整数),而带余除法的核心是关于余数r 的不等式:b r <≤0。证明a b |的基本手法是将a 分解为b 与一个整数之积,在 较为初级的问题中,这种数的分解常通过在一些代数式的分解中取特殊值而产生,下面两个
一类与正整数有关的恒等式的数列证法 昆明三中 耿留忠 众所周知,对于数列}{n a ,如果01=a ,当且1≥n 时,有01=-+n n a a ,那么数列}{n a 的每一项均为零;对于数列}{n b ,如果11=b ,当且1≥n 时,有11=+n n b b ,那么数列}{n b 的每一项均为1。运用这种思想我们可以找到与正整数n 有关的恒等式)()(n g n f =的一种证法。 (1)如果)(n f 是由多项式之和组成的,则构造数列}{n a ,使它的通项公式为)()(n g n f a n -=,这样就只要证明对一切*N n ∈,均有0=n a 。 (2) 如果)(n f 是由多项式之积组成的,且)(n f 不为零,则构造数列}{n b ,使它的通项公式为) ()(n g n f b n = ,这样就只要证明,均有1=n b 。 例1,证明:6 )12)(1(3212 222++=++++n n n n (高中数学选修 64p 例2) 证明:构造数列}{n a ,使=n a 6 )12)(1(3212222++-++++n n n n 则,06 )112)(11(1121=+?+-=a , 当1≥n 时,6 )12)(1(6]1)1(2][1)1)[(1()1(21++++++++-+=-+n n n n n n n a a n n 0]2)32)(2(66[612=++++-++=n n n n n n 所以,数列}{n a 的每一项均为零, 即对任意*N n ∈,均有 6 )12)(1(3212222++=++++n n n n 。 例2,证明:)12(531! 2)!2(-????=?n n n n (其中*N n ∈) (高中数学必修第二册下(A )142p ) 证明:本题等价于证明)12(5312)2()3)(2)(1(-?????=??+++n n n n n n
这个问题看起来不是很简单,需要设计一个算法: 先讲数学: 设: an=a+(n-1)*d (这里d=1) a1=a an=a+n-1 sn=(a1+an)n/2=(2a-1+n)/2 再回到这个编程上来: 我们的输入数据其实就是sn,需要找到以a开始的n个连续的递增数列使得和为sn。 这里我们可以用循环来判定,给定一个n,sn已知,就可以求出a,如果a为正整数那么就可以找到等差数列的首项,加上n给定,d=1,那么就可以写出这个和式子。 代码如下: #include
1、数列的概念:数列是一个定义域为正整数集N*(或它的有限子集{1,2,3,…,n })的特殊函数,数列的通项公式也就是相应函数的解析式。 2.等差数列的有关概念: (1)等差数列的判断方法:定义法:1(n n a a d d +-=为常数) 或11(2)n n n n a a a a n +--=-≥。 公式法:①通项b an a n +=;②前n 项和Bn An S n +=2 . (2)等差数列的通项:1(1)n a a n d =+-或()n m a a n m d =+-. 通项公式1(1)n a a n d =+-是n 的一次函数,以(n,a n )为坐标的一群离散点均匀地分布在直线上. 公 差d= 1 1 --n a a n 是相应直线的斜率.当d>0时,数列递增;当d<0时,数列递减;当d=0时,{a n }为常数数列. 提醒:n m ≠时n m a a d n m --=,可用来快速求公差. (3)等差数列的前n 和:1()2n n n a a S += ,1(1) 2 n n n S na d -=+ . 从函数的角度理解,Sn=na 1+2)1(-n n d 变形为Sn=2d n 2+(a 1-2 d )n ,当d≠0时是n 的二次函数(缺常数项),它的图象是 过原点的抛物线上的一群孤立点.点(n ,n Sn )* N n ∈)在一条直线上,此时,可以应用相应二次函数的图象了解Sn 的 增减变化及最值等问题。当d=0时,{an}是常数列,S n =na 1,此时,若a 1≠0,则S n 是关于n 的一次式;若a 1=0,则S n =0。 (4)等差中项:若,,a A b 成等差数列,则A 叫做a 与b 的等差中项,且2 a b A += 。 3.等差数列的性质: (1)当公差0d ≠时,等差数列的通项公式11(1)n a a n d dn a d =+-=+-是关于n 的一次函数,且斜率为公差d ; 前n 和211(1)()222 n n n d d S na d n a n -=+ =+-是关于n 的二次函数且常数项为0.提醒:可设等差数列的通项公式为b an a n +=,前n 和公式Bn An S n +=2 . (2)若公差0d >,则为递增等差数列,若公差0d <,则为递减等差数列,若公差0d =,则为常数列。 (3)当m n p q +=+时,则有q p n m a a a a +=+,特别地,当2m n p +=时,则有2m n p a a a +=. (4) 若{}n a 、{}n b 是等差数列,则{}n ka 、* {}(,)p nq a p q N +∈{}n n ka pb + (k 、p 是非零常数)、、? ?????n Sn 、 232,,n n n n n S S S S S -- ,…也成等差数列,而{}n a a 成等比数列;若{}n a 是等比数列,且0n a >,则{lg }n a 是等差数 列. (5)在等差数列{}n a 中,当项数为偶数2n 时,S S nd =偶奇 -, ),2(a a *1 n n N n n S S ∈≥= +欧 奇;项数为奇数21n -时,
学员姓名 年 级: 学科教师: 辅导科目: 授课日期 XX 年XX 月 XX 日 时 间 A / B / C / D / E / F 段 主 题 整数的运算性质 教学内容 1 d\7 施学习目标 1理解减法和除法运算性质,能运用减法和除法运算性质使一些计算更简便; 2.理解除法商不变性质,能运用商不变性质使一些计算更简便. 教法说明:上次课中的预习思考设置了三种巧算的方法,这里不需要讲解,本次课中的例题 对这三类巧算试题进行重点讲解. 、直接写出答案,看谁又快又准. 630 - 70 = 420 - 21 = 4X 23X 25 = 630 - 30 - 3 = 50 X 12 = 125 X 6X 8= 125X 16 = 24 X 25 = 350 - 25-2 = 35 - 7 X 5 = 640 - 32 = 42 X 7 - 42 = 教学设计:本部分设计的目的是想通过以上简单的题组训练,可以设置为学生相互间的 PK ,并检查学生对乘 除法运算中的巧算掌握如何。教师可以让学生分别分享下各自的计算方法,最后对每一题都整理出一个相对 简单的方法,重点是对乘除法运算中的运算律进行总结归纳,强调巧算的重要性。 参考答案:略 (此环节设计时间在 10—15分钟) 1到例题3分别
黃話精讲提升 (此环节设计时间在50—60分钟) 例题1:递等式计算(1) 687 —259—141 (2) 376 —( 176 + 27) 教法说明:首先让学生回顾上次课的预习思考第一小题,让学生总结下减法运算的性质:一个数连续减去两 个数,可以先把两个减数加起来,再从被减数里减去,用字母表示a-b-c = a- (b?c)。一个数减去两个数的和,可以从这个数里依次减去和中的每一个加数,用字母表示a-(b?c)=a-b-c 参考答案:(1)687—259—141 ( 2)376 —( 176+ 27) =687 —( 259 + 141) = 376 —176 —27 =687 —400 = 200—27 =287 =173 试一试:递等式计算(1) 765—254 + 135 —246 (2) 4509 —( 428 + 509)—572 参考答案:(1) 300; (2) 3000 例题 2 :计算(1) 6500- 25- 4 (2) 3700-( 25X 37) 教法说明:首先让学生回顾上次课的预习思考第二小题,让学生总结下除法运算的性质:一个数连续除以两个数,可以先把两个数乘起来,再去除被除数,用字母表示为:a“b“c = a“(b c);一个数除以两个数的 积,就等于这个数连续除以积里的两个因数,用字母表示为: 参考答案:(1) 6500-25 - 4 =6500-( 25 X 4) =6500 - 100 =65 试一试:计算(1) 78000 - 8 - 125 参考答案:(1) 78000 - 8- 125 a" (b c) = a~- b-' c (2) 3700 -( 25 X 37) =3700- 25 - 37 =3700- 37 - 25 =100 —25= 4 (2) 12000- 48 (2) 12000- 48
初中数学竞赛:连续正整数的性质 【内容提要】 一.两个连续正整数 1.两个连续正整数一 定是互质的,其商是既约分数。 2.两个连续正整数的积是偶数,且个位数只能是0,2,6。 3.两个连续正整数的和是奇数,差是1。 4.大于1的奇数都能写成两个连续正整数的和。例如3=1+2,79=39+40, 111=55+56。 二.计算连续正整数的个数 例如:不同的五位数有几个?这是计算连续正整数从10000到99999的个数,它是 99999-10000+1=90000(个) 1. n 位数的个数一般可表示为 9×10n-1(n 为正整数,100 =1) 例如一位正整数从1到9共9个(9×100), 二位数从10到99共90个 (9×101) 三位数从100到999共900个(9×102)…… 2.连续正整数从n 到m 的个 数是 m -n+1 把它推广到连续奇数、连续偶数、除以模m 有同余数的连续数的个数的计算,举例如下: 3. 从13到49的连续奇数的个数是 2 1349-+1=19 从13到49的连续偶数的个数是2 1448-+1=18 4. 从13到49能被3整除的正整数的个数是3 1548-+1=12 从13到49的正整数中除以3余1的个数是31349-+1=13 你能从中找到计算规律吗? 三.计算连续正整数的和 1. 1+2+3+……+n =(1+n )2 n (n 是正整数)
连续正整数从a 到b 的和 记作(a+b)2 1+-a b 把它推广到计算连续奇数、连续偶数、除以模m 有同余数的和,举例如下: 2. 11+13+15+…+55=(11+55)×2 23=759 (∵从11到55有奇数21155-+1=23个) 3. 11+14+17+…+53=(11+53)× 215=480 (∵从11到53正整数中除以3余2的数的个数共 31153-+1=15) 四. 计算由连续正整数连写的整数,各数位上的数字和 1. 123456789各数位上的数字和是(0+9)+(1+8)+…+(4+5) =9×5=45 2. 1234…99100计算各数位上的数字和可分组为:(0,99),(1,98), (2,97)…(48,51),(49,50)共有50个18,加上100中的1 ∴各数位上的数字和是18×50+1=901 五. 连续正整数的积 从1开始的n 个正整数的积1×2×3×…×n 记作n !,读作n 的阶乘 1. n 个连续正整数的积能被n !整除, 如11×12×13能被1×2×3整除;97×98×99×100能被4!整除; a (a+1)(a+2)…(a+n)能被(n+1)!整除。 2. n !含某因质数的个数。举例如下: ① 1×2×3×…×10的积中含质因数2的个数共8个 其中2,4,6,8,10都含质因数2 暂各计1个,共5个 其中4=22 含两个质因数2 增加了1个 其中8=23 含三个质因数2 再增加2个 ② 1×2×3×…×130的积中含质因数5的个数的计算法 5,10,15,…125,130 均含质因数5 暂各计1个,共26个 其中25,50,75,100均含52有两个5 各加1个, 共4个 其中125=53 含三个5 再增加2个