组合数学-输出所有路径-路径数问题
组合数学-输出所有路径
一．程序
#include
#include
int num1=1;//全局变量主要是为了在遍历二叉树的时候，只对无禁止线段的路径数计数。typedefstruct Point
{
intx,y;
};
typedefstruct node//二叉树
{
Point data;//二叉树的点坐标
intnum;//主要是为了求经过此结点的次数C(x+y,y);
struct node *lchl,*rchl;
} *NODE;
struct Line//禁止线段的结构体
{
Point start;
Point end;
};
boolbelongTo(Line l,Line line[],int n) //判断l是否属于禁止经过的线段，是则返回true; {
int i;
for(i=0;i { if(l.start.x==line[i].start.x &&l.start.y==line[i].start.y &&l.end.x==line[i].end.x &&l.end.y==line[i].end.y) return true; } return false; } int C(intm,int n) //返回组合数C(m,n) { double a=1.0,b=1.0; int c; int i; for(i=0;i a=a*(double)(m-i); for(i=n;i>0;i--) b=b*(double)i; c=a/b; return c; } void create(NODE &t,Point a) //创建二叉树，父结点坐标为(x,y),左子树结点坐标为(x,y-1),右子树结点坐标为(x-1,y)。直到所有叶子结点为(0,0)为止。 { Point r,l;//左结点，右结点数据 r.x=a.x;r.y=a.y-1; l.x=a.x-1;l.y=a.y; t=(node*)malloc(sizeof(node)); t->data=a ; t->num=C(a.x+a.y,a.y); if(r.x<0||r.y<0)//当x,y都小于0时停止创建结点 t->rchl=NULL; else create(t->rchl,r);//递归创建右结点 if(l.x<0||l.y<0) t->lchl=NULL; else create(t->lchl,l); } void prints(NODE T)//打印结点坐标(x,y) { if(T) { printf("(%d,",T->data.x); printf("%d)\n",T->data.y); } } void Ergodic(NODE T,intn,Line line[])//一次遍历，从根结点到叶子结点，找出其中一条路径{ intb,i;//b为此二叉树的层数 Line l,p;//父结点与子结点的一条线段，为了判断此线段是否属于禁止线段。 b=T->data.x+T->data.y; if(T)//结时点不为 { num1++;//上面的全局变量，如果此路径不含禁止线段，那么就直接加1, for(i=0;i { if(T->num>=1)//此结点的遍历次数>=1才继续遍历 { T->num--;//此结点的遍历次数-1 prints(T);//打印此结点信息 p.end=T->data; l.end=T->data; if(T->rchl&&T->rchl->num>=1)//如果左子树存在，而且可以继续遍历此接结点 { l.start=T->rchl->data; if(!belongTo(l,line,n))//父子结点构成的线段与禁止线段进行比较，不同，则继续 { T=T->rchl; } else//含有禁止线段，中断 { printf("含有禁止路径"); num1--; break; } } else if(T->lchl&&T->lchl->num>=1) { p.start=T->lchl->data; if(!belongTo(p,line,n)) { T=T->lchl; } else { printf("含有禁止路径"); num1--; break; } } } } } } void main() { int x=5,y=3,i,h,j;//x,y终点坐标 Point data;//终点坐标结点 data.x=x;data.y=y; NODE root;//数的根结点 create(root,data) ; //以根结点(x,y)创建二叉树 h=root->num;//总的路径数 int n=3;//禁止线段条数 Line *line=new Line[n]; line[0].start.x=2; line[0].start.y=2; line[0].end.x=3; line[0].end.y=2; line[1].start.x=4; line[1].start.y=2; line[1].end.x=5; line[1].end.y=2; line[2].start.x=6; line[2].start.y=2; line[2].end.x=6; line[2].end.y=3; line[3].start.x=7; line[3].start.y=2; line[3].end.x=7; line[3].end.y=3; for(i=0;i { printf("这是第%d条路径:\n",num1);//全局变量，如果找到一条可以通过的路径，就+1，其他数量不变。 Ergodic(root,4,line); } printf("\n") ; } 二.运行结果。 若所输出路径包含禁止线段，则如图所示： 三．整体思路： 根据二差树遍历，假设终点坐标为（x，y），那么二叉树的根节点就是（x，y），他的两个子节点就是（x-1，y），（x，y-1），以此类推，那么所有的叶子节点最终都会为（0,0）.如图所示： 第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分 6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分 11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分 E 中考数学核心知识专题复习----轨迹问题探究 符合一定条件的动点所形成的图形，或者说，符合一定条件的点的全体所组成的集合，叫做满足该条件的点的轨迹 六种常用的基本轨迹： ①到已知线段的两个端点距离相等的点的轨迹是这条线段的垂直平分线。 ②到已知角的两边距离相等的点的轨迹是这个角的平分线。 ③到已知直线的距离等于定长的点的轨迹是与这条直线平行，且与已知直线的距离等于定长的两条直线。 ④到两条平行线距离相等的点的轨迹是和这两条平行线平行且到这两条平行线距离相等的一条直线。 ⑤到定点的距离等于定长的点轨迹是与定点为圆心，定长为半径的圆。 ⑥和已知线段的两个端点的连线的夹角等于已知角的点的轨迹是以已知线段为弦，所含圆周角等于已知角的两段弧（端点除外）。 一、尺规作图：轨迹法确定动点位置 1）已知∠AOB,求作点P，使得点P到角两边距离相等，且满足OP=2 2）已知∠AOB和直线L,在直线L上确定点P，使得使得点P到角两边距离相等 3）已知∠AOB和线段CD,使得点P到角两边距离相等且满足PC=PD 4)已知线段AB和直线L，在直线L上确定点P使得∠APB=600 C A A D O B O B 1)2) L A L O B A B 3)4) 二交轨法应用 1.在正方形ABCD中，为AD边上一点，以BE边所在直线为折痕将?ABE对折之?PBE位置。若AB=2，且PC=1. 1)不全图形 B 2) 求 tan ∠ PCD 的值 A D B C 2．如图，在 △Rt ABC 中，∠CAB =90°，∠ACB=300，BC =8，D 为线段 AB 上的动点，过点 A 作 AH ⊥CD 于点 H ，连接 BH ，则 ② 求 AB 的长 ②求 BH 的最小值。 A D H C B 3．等边三角形 ABC 的边长为 6，在 AC ，BC 边上各取一点 E ，F ，连接 AF ，BE 相交于点 P ．且 AE =CF ； （1）求证：AF =BE ，并求∠APB 的度数； （2）若 AE =2，试求 AP AF 的值； （3）当点 E 从点 A 运动到点 C 时，试求点 P 经过的路径长． 4．如图，以 G （0，1）为圆心，半径为 2 的圆与 x 轴交于 A ，B 两点，与 y 轴交于 C ，D 两点，点 E 为⊙G 上一动点， CF ⊥ AE 于 F ．当点 E 从点 B 出发顺时针运动到点 D 时，点 F 所经过的路径长 y C G E A D 初中数学《最短路径问题》典型题型 知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。“饮马问题”，“造桥选址问题”。考的较多的还是“饮马问题”，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。解题总思路：找点关于线的对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧 例：已知：如图，A，B在直线L的两侧，在L上求一点P， 使得PA+PB最小。 解：连接AB,线段AB与直线L的交点P ，就是所求。（根据： 两点之间线段最短.） 二、两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A、B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短． 解：只有A、C、B在一直线上时，才能使AC+BC最小．作点A 关于直线“街道”的对称点A′，然后连接A′B，交“街道”于 点C，则点C就是所求的点． 三、一点在两相交直线内部 例：已知：如图A是锐角∠MON内部任意一点，在∠MON的两边 OM，ON上各取一点B，C，组成三角形，使三角形周长最小. 解：分别作点A关于OM，ON的对称点A′，A″；连接A′，A″，分别交OM，ON于 点B、点C，则点B、点C即为所求 分析：当AB、BC和AC三条边的长度恰好能够体现在一条直线上时，三角形的周长最小 例：如图，A.B两地在一条河的两岸，现要在河上建一座桥MN，桥造在何 A·M 处才能使从A到B的路径AMNB最短？（假设河的两岸是平行的直线，桥 N E 要与河垂直） 解：1.将点B 沿垂直与河岸的方向平移一个河宽到E ， 2.连接AE 交河对岸与点M, 则点M 为建桥的位置，MN 为所建的桥。 证明：由平移的性质，得 BN ∥EM 且BN=EM, MN=CD, BD ∥CE, BD=CE, 所以A.B 两地的距:AM+MN+BN=AM+MN+EM=AE+MN, 若桥的位置建在CD 处，连接AC.CD.DB.CE, 则AB 两地的距离为： AC+CD+DB=AC+CD+CE=AC+CE+MN, 在△ACE 中，∵AC+CE ＞AE, ∴AC+CE+MN ＞AE+MN,即AC+CD+DB ＞AM+MN+BN 所以桥的位置建在CD 处，AB 两地的路程最短。 例：如图，A 、B 是两个蓄水池，都在河流a 的同侧，为了方便灌溉作物，?要在河边建一个抽水站，将河水送到A 、B 两地，问该站建在 河边什么地方，?可使所修的渠道最短，试在图中确定该点。 作法：作点B 关于直线 a 的对称点点C,连接AC 交直线a 于点D ，则点D 为建抽水站的位置。 证明：在直线 a 上另外任取一点E ，连接AE.CE.BE.BD, ∵点B.C 关于直线 a 对称,点D.E 在直线 a 上，∴DB=DC,EB=EC, ∴AD+DB=AD+DC=AC, AE+EB=AE+EC 在△ACE 中，AE+EC ＞AC, 即 AE+EC ＞AD+DB 所以抽水站应建在河边的点D 处， 例：某班举行晚会，桌子摆成两直条(如图中的AO ，BO)，AO 桌面上摆满了桔子，OB 桌面上摆满了糖果，坐在C 处的学生小明先拿桔子再拿糖果，然后回到座位，请你帮助他设计一条行走路线，使其所走的总路程最短？ 作法：1.作点C 关于直线 OA 的对称点点D, 2. 作点C 关于直线 OB 的对称点点E, 3.连接DE 分别交直线OA.OB 于点M.N ， 则CM+MN+CN 最短 例：如图：C 为马厩，D 为帐篷，牧马人某一天要从马厩牵出马，先到草地边某一处牧马，再到河边饮马，然后回到帐篷，请你帮 · · C D A B E a 一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q 初中数学《最短路径问题》典型题型 知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。“饮马问题”，“造桥选址问题”。考的较多的还是“饮马问题”，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。 解题总思路：找点关于线的对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧 例：已知：如图，A ，B 在直线L 的两侧，在L 上求一点P ，使得PA+PB 最小。 解：连接AB,线段AB 与直线L 的交点P ，就是所求。（根据：两点之间线段最短.） 二、 两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A 、B 提供牛奶，奶站应建在什么地方，才能使从A 、B 到它的距离之和最短． 解：只有A 、C 、B 在一直线上时，才能使AC +BC 最小．作点A 关于直线“街道”的对称点A ′，然后连接A ′B ，交“街道”于点C ，则点C 就是所求的点． 三、一点在两相交直线内部 例：已知：如图A 是锐角∠MON 内部任意一点，在∠MON 的两边OM ，ON 上各取一点B ，C ，组成三角形，使三角形周长最小. 解：分别作点A 关于OM ，ON 的对称点A ′，A ″；连接A ′，A ″，分别交OM ，ON 于点B 、点C ，则点B 、点C 即为所求 分析：当AB 、BC 和AC 三条边的长度恰好能够体现在一条直线上时，三角形的周长最小 例：如图，A.B 两地在一条河的两岸，现要在河上建一座桥MN ，桥造在何处才能使从A 到B 的路径AMNB 最短？（假设河的两岸是平行的直线，桥要与河垂直） 解：1.将点B 沿垂直与河岸的方向平移一个河宽到E ， 2.连接AE 交河对岸与点M, 则点M 为建桥的位置，MN 为所建的桥。 A· B M N E 2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C. 运动轨迹 1、如图1，已知线段AB＝6，C、D是AB上两点，且AC＝DB＝1，P是线段CD上一动点，在AB同侧分别作等边三角 形APE和等边三角形PBF，G为线段EF的中点，点P由点C移动到点D时，G点移动的路径长度为_______． 2、正△ABC的边长为3cm，边长为1cm的正△RPQ的顶点R与点A重合，点P，Q分 别在AC，AB上，将△RPQ沿着边AB，BC，CA逆时针连续翻转（如图所示），直至点P 第一次回到原来位置，则点P运动的路径长为_______ cm．（结果保留π） 3、如图，AB为⊙O的直径，AB=8，点C为圆上任意一点，OD⊥AC于D， 当点C在⊙O上运动一周，点D运动的路径长为_______ 4、如图，一块边长为6cm的等边三角形木板ABC，在水平桌面上绕C点按顺 时针方向旋转到△A′B′C′的位置，则边AB的中点D运动的路径长是_______ 5、如图所示，扇形OAB从图①无滑动旋转到图②，再由图②到图③，∠O=60°，OA=1． （1）求O点所运动的路径长；（2）O点走过路径与直线L围成图形的面积． 6、如图，OA⊥OB，垂足为O，P、Q分别是射线OA、OB上两个动点，点C是线段PQ的中点，且PQ=4．则动点C运动形成的路径长是______ 7、如图，半径为2cm，圆心角为90°的扇形OAB的弧AB上有一运动的点P．从点P向半径OA引垂线PH交OA于点H．设△OPH的内心为I，当点P在弧AB上从点A运动到点B时，内心I所经过的路径长为______ ． 8、某数学兴趣小组对线段上的动点问题进行探究，已知AB=8． 问题思考： 如图1，点P为线段AB上的一个动点，分别以AP、BP为边在同侧作正方形APDC、BPEF． （1）当点P运动时，这两个正方形的面积之和是定值吗？若是，请求出；若不是，请求出这两个正方形面积之和的最小值．（2）分别连接AD、DF、AF，AF交DP于点K，当点P运动时，在△APK、△ADK、△DFK中，是否存在两个面积始终相等的三角形？请说明理由． 问题拓展： （3）如图2，以AB为边作正方形ABCD，动点P、Q在正方形ABCD的边上运动，且PQ=8．若点P从点A出发，沿A→B→C →D的线路，向点D运动，求点P从A到D的运动过程中，PQ的中点O所经过的路径的长． （4）如图3，在“问题思考”中，若点M、N是线段AB上的两点，且AM=BN=1，点G、H分别是边CD、EF的中点，请直接写出点P从M到N的运动过程中，GH的中点O所经过的路径的长及OM+OB的最小值． 9、如图，抛物线y=ax2+bx+3过点A（1，0），B（3，0），与y轴相交于点C． （1）求抛物线的解析式； （2）若点E为抛物线对称轴上的一点，请探索抛物线上是否存在点F，使以A，B，E，F为顶点的四边形为平行四边形？若存在，请求出所有点F的坐标；若不存在，请说明理由； （3）若点P为线段OC上的动点，连接BP，过点C作CN垂直于直线BP，垂足为N，当点P从点O运动到点C时，求点N运动路径的长． 初中数学[最短路径问题]典型题型及解题技巧 最短路径问题中,关键在于，我们善于作定点关于动点所在直线的对称点，或利用平移和展开图来处理。这对于我们解决此类问题有事半功倍的作用。理论依据：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”“立体图形展开图”。教材中的例题“饮马问题”，“造桥选址问题”“立体展开图”。考的较多的还是“饮马问题”。 知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。“饮马问题”，“造桥选址问题”。考的较多的还是“饮马问题”，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。 解题总思路：找点关于线的对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧 例：已知：如图，A，B在直线L的两侧，在L上求一点P，使得PA+PB 最小。 解：连接AB,线段AB与直线L的交点P ，就是所求。（根据：两点之间线段最短.） 二、两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A、B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短． 解：只有A、C、B在一直线上时，才能使AC+BC最小．作点A关于直线 “街道”的对称点A′，然后连接A′B，交“街道”于点C，则点C就是 所求的点． 三、一点在两相交直线内部 例：已知：如图A是锐角∠MON内部任意一点，在∠MON的两边OM，ON上各取一点B，C，组成三角形，使三角形周长最小. 解：分别作点A 关于OM ，ON 的对称点A ′，A ″；连接A ′，A ″，分别交OM ，ON 于点B 、点C ，则点B 、点C 即为所求 分析：当AB 、BC 和AC 三条边的长度恰好能够体现在一条直线上时，三角形的周长最小 例：如图，A.B 两地在一条河的两岸，现要在河上建一座桥MN ，桥造在何 处 才能使从A 到B 的路径AMNB 最短？（假设河的两岸是平行的直线，桥要与 河垂直） 解：1.将点B 沿垂直与河岸的方向平移一个河宽到E ， 2.连接AE 交河对岸与点M, 则点M 为建桥的位置，MN 为所建的桥。 证明：由平移的性质，得 BN ∥EM 且BN=EM, MN=CD, BD ∥CE, BD=CE, 所以A.B 两地的距:AM+MN+BN=AM+MN+EM=AE+MN, 若桥的位置建在CD 处，连接AC.CD.DB.CE, 则AB 两地的距离为： AC+CD+DB=AC+CD+CE=AC+CE+MN, 在△ACE 中，∵AC+CE ＞AE, ∴AC+CE+MN ＞AE+MN,即AC+CD+DB ＞AM+MN+BN 所以桥的位置建在CD 处，AB 两地的路程最短。 例：如图，A 、B 是两个蓄水池，都在河流a 的同侧，为了方便灌溉 作 物，?要在河边建一个抽水站，将河水送到A 、B 两地，问该站建在河边什么地方，?可使所修的渠道最短，试在图中确定该点。 · · C D A B E a A· B M N E ------------------------------------------------------------------------------------------------------------------------------ 1.（2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案： 2.（2.5分）设< L,*1,*2> 是代数系统，其中是*1,*2二元运算符，如果*1,*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L,*1,*2> 是格 正确 错误 正确答案： 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 正确 错误 正确答案： 4.（2.5分）零元是不可逆的 正确 错误 正确答案： 5.（2.5分）群中每个元素的逆元都是惟一的 正确 错误 正确答案： 6.（2.5分）设a,b,c是阿贝尔群< G,+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案： 7.（2.5分） < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案： 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案： 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案： 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案： 11.（2.5分）不含回路的连通图是树 1．如图，正方形ABCD 的边长是2，M 是AD 的中点，点E 从点A 出发，沿AB 运动到点B 停止．连接EM 并延长交射线CD 于点F ，过M 作EF 的垂线交射线BC 于点G ，连结EG 、FG ． （1）设AE ＝x 时，△EGF 的面积为y ，求y 关于x 的函数关系式，并写出自变量x 的取值范围； （2）P 是MG 的中点，请直接写出点P 运动路线的长． 2．如图①，在等腰梯形ABCD 中，AD ∥BC ，AE ⊥BC 于点E ，DF ⊥BC 于点F ．AD ＝2cm ，BC ＝6cm ，AE ＝4cm ．点P 、Q 分别在线段AE 、DF 上，顺次连接B 、P 、Q 、C ，线段BP 、PQ 、QC 、CB 所围成的封闭图形记为M ．若点P 在线段AE 上运动时，点Q 也随之在线段DF 上运动，使图形M 的形状发生改变，但面积始终为10cm 2．设EP ＝x cm ，FQ ＝y cm ，解答下列问题： （1）直接写出当x ＝3时y 的值； （2）求y 与x 之间的函数关系式，并写出自变量x 的取值范围； （3）当x 取何值时，图形M 成为等腰梯形？图形M 成为三角形？ （4）直接写出线段PQ 在运动过程中所能扫过的区域的面积． A B C D E F （备用图） A B C D E F Q P 图① 3．如图，在平面直角坐标系中，矩形OABC 的两边OA 、OC 分别在x 轴、y 轴的正半轴上，OA ＝4，OC ＝2．点P 从点O 出发，沿x 轴以每秒1个单位长的速度向点A 匀速运动，当点P 到达点A 时停止运动，设点P 运动的时间是t 秒．将线段CP 的中点绕点P 按顺时针方向旋转90°得点D ，点D 随点P 的运动而运动，连接DP 、DA ． （1）请用含t 的代数式表示出点D 的坐标； （2）求t 为何值时，△DP A 的面积最大，最大为多少？ （3）在点P 从O 向A 运动的过程中，△DP A 能否成为直角三角形？若能，求t 的值；若不能，请说明理由； （4）请直接写出随着点P 的运动，点D 运动路线的长. 4.如图，直角坐标系中，已知点A （2，4），B （5，0），动点P 从B 点出发沿BO 向终点O 运动，动点Q 从A 点出发沿AB 向终点B 运动．两点同时出发，速度均为每秒1个单位，设从出发起运动了x 秒． （1）Q 点的坐标为( , )（用含x 的代数式表示）； （2）当x 为何值时，△APQ 是一个以AP 为腰的等腰三角形？ （3）记PQ 的中点为G ．请你直接写出点G 随点P ，Q 运动所经过的路线的长度． 货物配送问题 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。 针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为40.5007小时，费用为4685.6元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为26.063小时，费用为4374.4元。 针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证，排除了4吨货车的使用。题目没有规定车子不能变向，所以认为车辆可以掉头。然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为 19.6844小时，费用为4403.2。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题： 离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 勾股定理中最短路径问题专题 一、同步知识梳理 1、勾股数：满足a2＋b2＝c2的3个正整数a、b、c称为勾股数． （1）由定义可知，一组数是勾股数必须满足两个条件： ①满足a2＋b2＝c2 ②都是正整数．两者缺一不可． （2）将一组勾股数同时扩大或缩小相同的倍数所得的数仍满足a2＋b2＝c2 (但不一定是勾股数)，例如：3、4、5是一组勾股数，但是以0.3 cm、0.4 cm、0.5 cm为边长的三个数就不是勾股数。 二、同步题型分析 1、等腰三角形的周长是20 cm，底边上的高是6 cm，求它的面积. 2、（1）在△ABC中，∠C＝90°，AB＝6，BC＝8，DE垂直平分AB，求BE的长. （2）在△ABC中，∠C＝90°，AB＝6，BC＝8，AE平分∠CAE，ED⊥AB,求BE的长. （3）如图，折叠长方形纸片ABCD，是点D落在边BC上的点F处，折痕为AE，AB=CD=6，AD=BC=10，试求EC的长度. 一、专题精讲 知识总结：长方体： （1）长方体的长、宽、高分别为a、b、c；（2）求如图所示的两个对顶点的最短距离d。 E D A C B D E A C B A B A 1B 1D C D 1C 1214 （2）长方体盒子表面小虫爬行的最短路线d 是22c b a ++）（、22b c a ++）（、2 2a c b ++）（ 中最小者的值。 圆柱体： （1）圆柱体的高是h 、半径是r ；（2）要求圆柱体的对顶点的最短距离。 圆柱体盒子外小虫爬行的最短路线d ； 两条路线比较：其一、AC+BC 即高+直径 ； 其二、圆柱表面展开后线段AB=2 2r h +的长. 题型二、长方体 例题1、如图，一只蚂蚁从实心长方体的顶点A 出发，沿长方体的表面爬到对角顶点C 1处（三条棱长如图所示），问怎样走路线最短？最短路线长为 . 例题2、如图，长方体的长为15，宽为10，高为20，点B 离点C 的距离为5，一只蚂蚁如果要沿着长方体的表面从点A 爬到点B ，需要爬行的最短距离是 。 B A A B 华东交通大学数学建模 2012年第一次模拟训练题 所属学校：华东交通大学（ECJTU ） 参赛队员：胡志远、周少华、蔡汉林、段亚光、 李斌、邱小秧、周邓副、孙燕青 指导老师：朱旭生（博士） 摘要： 本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求解问题上，问题特点是随机性比较强。 根据不同建模类型 针对问题一 ，我们直接采用Dijkstra 算法（包括lingo 程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。 针对问题二，我们首先利用prim 算法求解得到一棵最小生成树： 121098436751V V V V V V V V V V V →→→→→→→→→→ 再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→ 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线： 121098436751V V V V V V V V V V V →→→→→→→→→→。 针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）； 针对问题四， 离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G= 动点问题讲义 1、如图1，已知线段 AB= 6, C D 是AB 上两点，且 AC = DB= 1, P 是线段CD 上一动点，在 AB 同侧 分别作等边三角形 APE 和等边三角形PBF G 为线段EF 的中点，点P 由点C 移动到点D 时，G 点移 动的路径长度为 . 2、正△ ABC 的边长为3cm,边长为1cm 的正△ RPQ 的顶点R 与点A 重合，点P, Q 分别在AC, AB 上，将△ RPQ 沿着边AB BC, CA 逆时针连续翻转(如图所示)，直至点 P 第一次回到原来位置，则点 P 运动的路径长为 3、如图，AB 为O O 的直径，AB=8,点C 为圆上任意一点，ODL AC 于D,当点C 在O 0上运动一周，点 D 运动 的路径长为 ______________ 4、如图，一块边长为 6cm 的等边三角形木板 ABC 在水平桌面上绕 C 点按顺时针方向旋转到厶 A B ' C'的 位置，则边AB 的中点D 运动的路径长是 ____________________ 5、如图所示，扇形 OAB 从图①无滑动旋转到图②，再由图②到图③，/ 0=60°, OA=1. (1 )求O 点所运动的路径长； (2) O 点走过路径与直线 L 围成图形的面积 .cm .(结果保留n) O A O 图L 图2 C 6、如图，0从0B,垂足为0, P、Q分别是射线OA 0B上两个动点，点C是线段PQ的中点，且PQ=4则动 点C运动形成的路径长是_______ 90°的扇形0AB的弧AB上有一运动的点P.从点P向半径0A引垂线PH交当点 P在弧AB上从点A运动到点B时，内心I所经过的路径长为. &如图，正方形ABC啲边长是2, M是AD的中点，点E从点A出发，沿AB运动到点B停止?连接EM并延长交射线CD于点F,过M作EF的垂线交射线BC于点G连结EG FG (1 )设AE= x时，△ EGF的面积为y,求y关于x的函数关系式，并写出自变量x的取值范围； (2) P是MG的中点，请直接写出点P运动路线的长. 平面几何轨迹问题分类例析 近年来，在各地中考中出现了一类求动点轨迹的路径长的问题，由于较难确定动点轨迹的形状，往往导致学生无从下手.本文以部分中考题为例，就如何确定动点轨迹的形状进行分类解析，供读者参考. 一、直线型动点轨迹 事实上，要说明一动点轨迹为直线型(直线、射线或线段)，必须证明两点:第一、该轨迹恒过一定点(确定位置);第二、轨迹上任一点与该定点的连线和一定直线的夹角为定值或平行(明确方向). 例1 (2013年湖州)如图1，已知点A 是第一象限内横坐标为AN x ⊥轴于点M ，交直线y x =-于点N .若点P 是线段ON 上的一个动点，30APB ∠=?, BA PA ⊥,则点P 在线段ON 上运动时，A 点不变，B 点随之运动.求当点P 从点O 运动到 点N 时，点B 运动的路径长是___. 图1 解析 如图2，由点P 位于O 、N 时，点B 所对应的位置0B 、n B 以及点P 在线段OC 上运动，可猜想点B 的轨迹是线段0n B B .如何证明呢? 显然，点B 的轨迹已经过0B 点，下面只需证明0AB B ∠为定值，即证明它与某一个定角相等即可. 观察可得，APN ∠就是与0AB B ∠相等的 定角，再由两角的位置特征和题设条件，不难 想到用三角形相似来证明两角相等. 由0tan30,tan30AB AO AB AP =?=?，得0::tan30AB AO AB AP ==? 又易知0OAC B AB ∠=∠ ,得0AB B ?∽AOP ?, 所以0AB B AOP ∠=∠为定值. 故点B 在线段0n B B 上， 即线段0n B B 就是点B 运动的路径(或轨迹). 同理可证 0n A B B ?∽AON ?，且相似比为 t a n 3?， 则 0t a n 22 n B B O N = ?= 图2 注 例1利用角来确定动点的运动方向，还可用与定直线平行确定动点的运动方向. 例2 (2010年桂林)如图3，已知AB =10，点C 、D 在线段AB 上，且2AC DB ==. P 是线段CD 上的动点，分别以AP 、PB 为边在线段AB 的同侧作等边AEP ?和等边PFB ?，连结EF ，设EF 的中点为G .当点P 从点C 运动到点D 时，点G 移动路径的长 是 . 图3 解析 如图4，分别延长AE 、BF 交于点H ，由60EAP FBP ∠=∠=?可知，当点P 在线段CD 上移动时，点E 、F 分别在线段AH 、BH 上移动. 图4 由60A FPB ∠=∠=?，知AH //PF , 同理BH //PE . 北京邮电大学 离散数学 第一次阶段作业 判断题 1. 集合A上的任一运算对A是封闭的。【答案：A】 A. 正确 B. 错误 2. 设G;·是群，如果对于任意a,b?G，有a·b2=a2·b2，则G;·是阿贝尔群。【答案：A】 A. 正确 B. 错误 3. 设a,b是群G;·的元素，则a·b?1=a?1·b?1。【答案：B】 A. 正确 B. 错误 4. 0,1,2,3,4,max,min是格。【答案：A】 A. 正确 B. 错误 5. 设集合A=a,b，则?,a,b,A,∪,∩是格。【答案：A】 A. 正确 B. 错误 单项选择题 1. 设集合A={1,2,3,4,…,10}，则下面定义的哪种运算关于集合A不是封闭的。【答案：D】 A. x°y=max x,y B. x°y=min x,y C. x°y=GCD x,y，即x,y的最小公约数 D. x°y=LCM x,y，即x,y的最小公倍数 2. 循环群Z,+的所有生成元为【答案：D】 A. 1,0 B. -1,2 C. 1,2 D. 1,-1 3. 循环群I5,?5的所有之群为【答案：C】 A. I5,?5 B. 0,?5 C. I5,?5且0,?5 D. ? 4. 设代数系统A,·，则下面结论成立的是【答案：C】 A. 如果A,·是群，则A,·是阿贝尔群 B. 如果A,·是阿贝尔群，则A,·是循环群 C. 如果A,·是循环群，则A,·是阿贝尔群 D. 如果A,·是阿贝尔群群，则A,·必不是循环群 5. 下列代数系统G,?中，哪一个不构成群【答案：D】 A. G=1,10，*是模 11 乘法 B.G=0,1,2，*是模 3 乘法 C.G=Q有理数集，*是普通加法 D.G=Q，*普通乘法离散数学第二次在线作业
中考数学专题复习-轨迹问题
初中数学《最短路径问题》典型题型复习
《离散数学》第2次作业
初中数学《最短路径问题》典型题型复习
2013年4月考试离散数学第二次作业
中考数学轨迹问题精选
初中数学最短路径问题典型题型及解题技巧
中石油北京19春《离散数学》第二次在线作业
中考数学轨迹问题
数学建模大赛-货物运输问题
离散数学作业 (2)
人教版八年级数学下册 第17章 勾股定理中最短路径问题专题
数学建模运输问题
电大离散数学作业答案作业答案
中考数学轨迹问题集锦
平面几何轨迹问题分类例析
北邮离散数学第二次阶段作业
- 2013年9月份考试离散数学第二次作业
- 离散数学2017+第二次作业
- 交大网络学院离散数学第二次作业
- 《离散数学》第2次作业
- 离散数学第一第二次作业
- 19秋中石油北京校区离散数学第二次在线作业
- 华工离散数学第二次作业
- 2020年中国石油大学北京网络学院 离散数学-第二次在线作业 参考答案
- 2014年9月份考试离散数学第二次作业
- 离散数学作业 (2)
- 离散数学第二次作业
- 离散数学 第二次作业
- 离散数学作业 (2)
- 离散数学第二次在线作业
- 离散数学形成性考核作业
- 北邮离散数学第二次阶段作业
- 离散数学第一第二次作业
- 西南大学2016春《离散数学》第2次作业
- 离散数学第二次作业讲解
- 中石油北京19春《离散数学》第二次在线作业