首页 > 搜索 > 26乘以1725用简算算法,算法设计与分析

26乘以1725用简算算法,算法设计与分析

互联网 2020-10-23 15:34:34
在线算命,八字测算命理
1 1.1 第1章─概论 2 3 1.1.1 练习题 4 1. 下列关于算法的说法中正确的有( )。 5 Ⅰ.求解某一类问题的算法是唯一的 6 Ⅱ.算法必须在有限步操作之后停止 7 Ⅲ.算法的每一步操作必须是明确的,不能有歧义或含义模糊 8 Ⅳ.算法执行后一定产生确定的结果 9 A. 1个 B.2个 C.3个 D.4个10 2. T(n)表示当输入规模为n时的算法效率,以下算法效率最优的是( )。11 A.T(n)= T(n-1)+1,T(1)=1B.T(n)= 2n212 C.T(n)= T(n/2)+1,T(1)=1D.T(n)=3nlog2n13 3. 什么是算法?算法有哪些特征?14 4. 判断一个大于2的正整数n是否为素数的方法有多种,给出两种算法,说明其中 15 一种算法更好的理由。16 5. 证明以下关系成立:17 (1)10n2-2n=?(n2)18 (2)2n+1=?(2n)19 6. 证明O(f(n))+O(g(n))=O(max{f(n),g(n)}) 。20 7. 有一个含n(n>2)个整数的数组a,判断其中是否存在出现次数超过所有元素一 21 半的元素。22 8. 一个字符串采用string对象存储,设计一个算法判断该字符串是否为回文。23 9. 有一个整数序列,设计一个算法判断其中是否存在两个元素和恰好等于给定的整 24 数k。25 10. 有两个整数序列,每个整数序列中所有元素均不相同。设计一个算法求它们的公 共元素,要求不使用STL的集合算法。26 11. 正整数n(n>1)可以写成质数的乘积形式,称为整数的质因数分解。例如, 12=2*2*3,18=2*3*3,11=11。设计一个算法求n这样分解后各个质因数出现的次数,采 用vector向量存放结果。27 12. 有一个整数序列,所有元素均不相同,设计一个算法求相差最小的元素对的个 数。如序列4、1、2、3的相差最小的元素对的个数是3,其元素对是(1,2),(2,3), (3,4)。28 13. 有一个map容器,其中已经存放了较多元素。设计一个算法求出其 中重复的value并且返回重复value的个数。29 14. 重新做第10题,采用map容器存放最终结果。30 15. 假设有一个含n(n>1)个元素的stack栈容器st,设计一个算法出栈从栈顶 31 到栈底的第k(1≤k≤n)个元素,其他栈元素不变。  32 33 算法设计34 35 1.1.2 练习题参考答案36 1. 答:由于算法具有有穷性、确定性和输出性,因而Ⅱ、Ⅲ、Ⅳ正确,而解决某一 37 类问题的算法不一定是唯一的。答案为C。38 2. 答:选项A的时间复杂度为O(n)。选项B的时间复杂度为O(n2)。选项C的时间 39 复杂度为O(log2n)。选项D的时间复杂度为O(nlog2n)。答案为C。40 3. 答:算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输 41 入性和输出性5个重要特征。42 4. 答:两种算法如下:43 #include 44 #include 45 bool isPrime1(int n) //方法146 { for (int i=2;in/2) 100 return true; 101else 102 return false; 103 } 104 void main() 105 { int a[]={2,2,2,4,5,6,2}; 106int n=sizeof(a)/sizeof(a[0]); 107int x; 108if (solve(a,n,x)) 109 printf("出现次数超过所有元素一半的元素为%d\n",x); else 110 printf("不存在出现次数超过所有元素一半的元素\n");} 111 上述程序的执行结果如图1.1所示。 112 113 114 115 116 图1.1程序执行结果 117 8. 解:采用前后字符判断方法,对应的程序如下: 118 #include 119 #include 120 using namespace std; 121 bool solve(string str)//判断字符串str是否为回文{ int i=0,j=str.length()-1; 122while (i0) 260{ e.p=i; 261 e.pc=ic; 262 v.push_back(e); 263} 264ic=0; 265i++; 266 } 267} while (n>1 || ic!=0); 268 } 269 void disp(vector &v)//输出v 270 { vector::iterator it; 271for (it=v.begin();it!=v.end();++it) 272 printf("质因数%d出现%d次\n",it->p,it->pc); 273 } 274 275 6  276 277 278 void main() 279 { vector v; 280int n=100; 281printf("n=%d\n",n); 282solve(n,v); 283disp(v); 284 } 285 上述程序的执行结果如图1.5所示。 286 287 第1章概论 288 289 290 291 292 293 图1.5程序执行结果 294 12. 解:先递增排序,再求相邻元素差,比较求最小元素差,累计最小元素差的个 295 数。对应的程序如下: 296 #include 297 #include 298 #include 299 using namespace std; 300 int solve(vector &myv) //求myv中相差最小的元素对的个数 301 { sort(myv.begin(),myv.end()); //递增排序 302int ans=1; 303int mindif=myv[1]-myv[0]; 304for (int i=2;i0) 379 mymap[i]=ic; 380ic=0; 381i++; 382 } 383} while (n>1 || ic!=0); 384 } 385 void disp(map &mymap) //输出mymap 386 { map::iterator it; 387for (it=mymap.begin();it!=mymap.end();++it) 388 printf("质因数%d出现%d次\n",it->first,it->second);} 389 void main() 390 { map mymap; 391int n=12345; 392printf("n=%d\n",n); 393solve(n,mymap); 394disp(mymap); 395 } 396 上述程序的执行结果如图1.8所示。 397 398 399 400 401 402 403 图1.8程序执行结果 404 15. 解:栈容器不能顺序遍历,为此创建一个临时tmpst栈,将st的k个元素出栈并 405 进栈到tmpst中,再出栈tmpst一次得到第k个元素,最后将栈tmpst的所有元素出栈并进 栈到st中。对应的程序如下: 406 #include 407 #include 408 using namespace std; 409 int solve(stack &st,int k)//出栈第k个元素 410 { stack tmpst; 411int e; 412for (int i=0;i1 480 4. 采用特征方程方法求解以下递归方程: 481 H(0)=0 482 H(1)=1 483 H(2)=2 484 H(n)=H(n-1)+9H(n-2)-9H(n-3) 当n>2 485 5. 采用递归树方法求解以下递归方程: 486 T(1)=1 487 T(n)=4T(n/2)+n当n>1 488 6. 采用主方法求解以下题的递归方程。 489 T(n)=1当n=1 490 T(n)=4T(n/2)+n2当n>1 491 7. 分析求斐波那契f(n)的时间复杂度。 492 8. 数列的首项a1=0,后续奇数项和偶数项的计算公式分别为a2n=a2n-1+2,a2n+1=a2n- 493 1+a2n-1,写出计算数列第n项的递归算法。 494 9. 对于一个采用字符数组存放的字符串str,设计一个递归算法求其字符个数(长 495 度)。 496 10. 对于一个采用字符数组存放的字符串str,设计一个递归算法判断str是否为回 497 文。 498 11. 对于不带头结点的单链表L,设计一个递归算法正序输出所有结点值。 499 12. 对于不带头结点的单链表L,设计一个递归算法逆序输出所有结点值。 500 13. 对于不带头结点的非空单链表L,设计一个递归算法返回最大值结点的地址(假 501 设这样的结点唯一)。 502 14. 对于不带头结点的单链表L,设计一个递归算法返回第一个值为x的结点的地 503 址,没有这样的结点时返回NULL。 504 15. 对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点。 505 16. 假设二叉树采用二叉链存储结构存放,结点值为int类型,设计一个递归算法求 二叉树bt中所有叶子结点值之和。 506 17. 假设二叉树采用二叉链存储结构存放,结点值为int类型,设计一个递归算法求 二叉树bt中所有结点值大于等于k的结点个数。 507 18. 假设二叉树采用二叉链存储结构存放,所有结点值均不相同,设计一个递归算法 求值为x的结点的层次(根结点的层次为1),没有找到这样的结点时返回0。 508 509 510 11  511 512 算法设计 513 514 1.2.2练习题参考答案 515 1. 答:一个f函数定义中直接调用f函数自己,称为直接递归。一个f函数定义中调 516 用g函数,而g函数的定义中调用f函数,称为间接递归。消除递归一般要用栈实现。 517 2. 答:递归函数f(n,m)中,n是非引用参数,m是引用参数,所以递归函数的状态为 518 (n)。程序执行结果如下: 519 调用f(3,3)前,n=4,m=4 520 调用f(1,2)前,n=2,m=3 521 调用f(0,1)后,n=1,m=2 522 调用f(2,1)后,n=3,m=2 523 3. 解:求T(n)的过程如下: 524 T(n)=T(n-1)+n=[T(n-2)+n-1)]+n=T(n-2)+n+(n-1) 525 =T(n-3)+n+(n-1)+(n-2) 526 =… 527 =T(1)+n+(n-1)+…+2 528 =n+(n-1)+ +…+2+1=n(n+1)/2=O(n2)。 529 4. 解:整数一个常系数的线性齐次递推式,用xn代替H(n),有:xn=xn-1+9xn-2-9xn-3, 530 两边同时除以xn-3,得到:x3=x2+9x-9,即x3-x2-9x+9=0。 531 x3-x2-9x+9=x(x2-9)-(x2-9)=(x-1)(x2-9)=(x-1)(x+3)(x-3)=0。得到r1=1,r2=-3,r3=3 532 则递归方程的通解为:H(n)=c1+c2(-3)n+c33n 533 代入H(0)=0,有c1+c2+c3=0 534 代入H(1)=1,有c1-3c2+3c3=1 535 代入H(2)=2,有c1+9c2+9c3=2 536 求出:c1=-1/4,c2=-1/12,c3=1/3,H(n)=c1+c2(-3)n+c33n=((?1)。 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 12  556 557 558 559 560 561 562 高度h为log2n+1 563 564 565 566 567 568 569 570 (n/22) 571 …… 572 573 574 575 576 577 (n/2) 578 579 (n/22) 580 … 581 582 第1章概论 583 584 n 585 (n/2)(n/2)(n/2) 586 587 (n/22) 588 … 589 590 591 592 593 n 594 2n 595 596 22n 597 598 11n 599 图1.10 一棵递归树 600 6. 解:采用主方法求解,这里a=4,b=2,f(n)=n2。 601 因此,??==n2,它与f(n)一样大,满足主定理中的情况(2),所以T(n)= 602 log2n) 603 7. 解:设求斐波那契f(n)的时间为T(n),有以下递推式: 604 T(1)=T(2) 605 T(n)=T(n-1)+T(n-2)+1 当n>2 606 其中,T(n)式中加1表示一次加法运算的时间。 607 不妨先求T1(1)=T1(2)=1,T1(n)=T1(n-1)+T1(n-2),按《教程》例2.14的方法可以求 608 出: 609 nn 610 T1(n)=≈= 611 612 所以T(n)=T1(n)+1≈+1=O(φn),其中φ=。 613 8. 解:设f(m)计算数列第m项值。 614 当m为偶数时,不妨设m=2n,则2n-1=m-1,所以有f(m)=f(m-1)+2。 615 当m为奇数时,不妨设m=2n+1,则2n-1=m-2,2n=m-1,所以有f(m)=f(m-2)+f(m- 616 1)-1。 617 对应的递归算法如下: 618 int f(int m) 619 { if (m==1) return 0; 620if (m%2==0) 621 return f(m-1)+2; 622else 623 return f(m-2)+f(m-1)-1; 624 } 625 9. 解:设f(str)返回字符串str的长度,其递归模型如下: 626 f(str)=0 当*str='\0'时 627 f(str)=f(str+1)+1其他情况 628 对应的递归程序如下: 629 13  630 631 算法设计 632 633 #include 634 using namespace std; 635 int Length(char *str) //求str的字符个数 636 { if (*str=='\0') 637 return 0; 638else 639 return Length(str+1)+1; 640 } 641 void main() 642 { char str[]="abcd"; 643cout data; f(L->next); 当L≠NULL时 694 对应的递归程序如下: 695 #include "LinkList.cpp" //包含单链表的基本运算算法 696 void dispLink(LinkNode *L)//正序输出所有结点值 697 { if (L==NULL) return; 698else 699{ printf("%d ",L->data); 700 dispLink(L->next); 701} 702 } 703 void main() 704 { int a[]={1,2,5,2,3,2}; 705int n=sizeof(a)/sizeof(a[0]); 706LinkNode *L; 707CreateList(L,a,n); //由a[0..n-1]创建不带头结点的单链表 printf("正向L: "); 708dispLink(L); printf("\n"); 709Release(L);//销毁单链表 710 } 711 上述程序的执行结果如图1.13所示。 712 713 714 715 716 图1.13程序执行结果 717 12. 解:设f(L)逆序输出单链表L的所有结点值,其递归模型如下: 718 f(L) ≡ 不做任何事情 当L=NULL 719 f(L) ≡ f(L->next); 输出L->data 当L≠NULL时 720 对应的递归程序如下: 721 #include "LinkList.cpp" //包含单链表的基本运算算法 722 void Revdisp(LinkNode *L)//逆序输出所有结点值 723 { if (L==NULL) return; 724 15  725 726 727else 728{ Revdisp(L->next); 729 printf("%d ",L->data); 730} 731 } 732 void main() 733 { int a[]={1,2,5,2,3,2}; 734int n=sizeof(a)/sizeof(a[0]); 735LinkNode *L; 736CreateList(L,a,n); 737printf("反向L: "); 738Revdisp(L); printf("\n"); 739Release(L); 740 } 741 上述程序的执行结果如图1.14所示。 742 743 744 算法设计 745 746 747 748 749 图1.14程序执行结果 750 13. 解:设f(L)返回单链表L中值最大结点的地址,其递归模型如下: 751 f(L) = L当L只有一个结点时 752 f(L) = MAX{f(L->next),L->data} 其他情况 753 对应的递归程序如下: 754 #include "LinkList.cpp" //包含单链表的基本运算算法 755 LinkNode *Maxnode(LinkNode *L) //返回最大值结点的地址 756 { if (L->next==NULL) 757 return L;//只有一个结点时 758else 759{ LinkNode *maxp; 760 maxp=Maxnode(L->next); 761 if (L->data>maxp->data) 762return L; 763 else 764return maxp; 765} 766 } 767 void main() 768 { int a[]={1,2,5,2,3,2}; 769int n=sizeof(a)/sizeof(a[0]); 770LinkNode *L,*p; 771CreateList(L,a,n); 772p=Maxnode(L); 773printf("最大结点值: %d\n",p->data); 774Release(L); 775 776 16  777 778 779 } 780 上述程序的执行结果如图1.15所示。 781 782 第1章概论 783 784 785 786 787 图1.15程序执行结果 788 14. 解:设f(L,x)返回单链表L中第一个值为x的结点的地址,其递归模型如下: 789 f(L,x) = NULL当L=NULL时 790 f(L,x) = L当L≠NULL且L->data=x时 791 f(L,x) = f(L->next,x)其他情况 792 对应的递归程序如下: 793 #include "LinkList.cpp" //包含单链表的基本运算算法 794 LinkNode *Firstxnode(LinkNode *L,int x) //返回第一个值为x的结点的地址 795 { if (L==NULL) return NULL; 796if (L->data==x) 797 return L; 798else 799 return Firstxnode(L->next,x); 800 } 801 void main() 802 { int a[]={1,2,5,2,3,2}; 803int n=sizeof(a)/sizeof(a[0]); 804LinkNode *L,*p; 805CreateList(L,a,n); 806int x=2; 807p=Firstxnode(L,x); 808printf("结点值: %d\n",p->data); 809Release(L); 810 } 811 上述程序的执行结果如图1.16所示。 812 813 814 815 816 图1.16程序执行结果 817 15. 解:设f(L,x)删除单链表L中第一个值为x的结点,其递归模型如下: 818 f(L,x) ≡ 不做任何事情当L=NULL 819 f(L,x) ≡ 删除L结点,L=L->next当L≠NULL且L->data=x 820 f(L,x) ≡ f(L->next,x)其他情况 821 对应的递归程序如下: 822 823 17  824 825 算法设计 826 827 #include "LinkList.cpp"//包含单链表的基本运算算法 828 void Delfirstx(LinkNode *&L,int x) //删除单链表L中第一个值为x的结点{ if (L==NULL) return; 829if (L->data==x) 830{ LinkNode *p=L; 831 L=L->next; 832 free(p); 833} 834else 835 Delfirstx(L->next,x); 836 } 837 void main() 838 { int a[]={1,2,5,2,3,2}; 839int n=sizeof(a)/sizeof(a[0]); 840LinkNode *L; 841CreateList(L,a,n); 842printf("删除前L: "); DispList(L); 843int x=2; 844printf("删除第一个值为%d的结点\n",x); 845Delfirstx(L,x); 846printf("删除后L: "); DispList(L); 847Release(L); 848 } 849 上述程序的执行结果如图1.17所示。 850 851 852 853 854 855 图1.17程序执行结果 856 16. 解:设f(bt)返回二叉树bt中所有叶子结点值之和,其递归模型如下: 857 f(bt)=0当bt=NULL 858 f(bt)=bt->data 当bt≠NULL且bt结点为叶子结点 859 f(bt)=f(bt->lchild)+f(bt->rchild)其他情况 860 对应的递归程序如下: 861 #include "Btree.cpp" //包含二叉树的基本运算算法 862 int LeafSum(BTNode *bt) //二叉树bt中所有叶子结点值之和 863 { if (bt==NULL) return 0; 864if (bt->lchild==NULL && bt->rchild==NULL) 865 return bt->data; 866int lsum=LeafSum(bt->lchild); 867int rsum=LeafSum(bt->rchild); 868return lsum+rsum; 869 } 870 void main() 871 872 18  873 第1章概论 874 875 { BTNode *bt; 876Int a[]={5,2,3,4,1,6};//先序序列 877Int b[]={2,3,5,1,4,6};//中序序列 878int n=sizeof(a)/sizeof(a[0]); 879bt=CreateBTree(a,b,n);//由a和b构造二叉链bt printf("二叉树bt:"); DispBTree(bt); printf("\n"); printf("所有叶子结点值之和: %d\n",LeafSum(bt)); 880DestroyBTree(bt); //销毁树bt 881 } 882 上述程序的执行结果如图1.18所示。 883 884 885 886 887 888 图1.18程序执行结果 889 17. 解:设f(bt,k)返回二叉树bt中所有结点值大于等于k的结点个数,其递归模型 890 如下: 891 f(bt,k)=0当bt=NULL 892 f(bt,k)=f(bt->lchild,k)+f(bt->rchild,k)+1当bt≠NULL且bt->data≥k 893 f(bt,k)=f(bt->lchild,k)+f(bt->rchild,k)其他情况 894 对应的递归程序如下: 895 #include "Btree.cpp"//包含二叉树的基本运算算法 896 int Nodenum(BTNode *bt,int k)//大于等于k的结点个数 897 { if (bt==NULL) return 0; 898int lnum=Nodenum(bt->lchild,k); 899int rnum=Nodenum(bt->rchild,k); 900if (bt->data>=k) 901 return lnum+rnum+1; 902else 903 return lnum+rnum; 904 } 905 void main() 906 { BTNode *bt; 907Int a[]={5,2,3,4,1,6}; 908Int b[]={2,3,5,1,4,6}; 909int n=sizeof(a)/sizeof(a[0]); 910bt=CreateBTree(a,b,n); //由a和b构造二叉链bt 911printf("二叉树bt:"); DispBTree(bt); printf("\n"); 912int k=3; 913printf("大于等于%d的结点个数: %d\n",k,Nodenum(bt,k)); 914DestroyBTree(bt);//销毁树bt 915 } 916 上述程序的执行结果如图1.19所示。 917 918 919 19  920 921 算法设计 922 923 924 925 926 927 928 图1.19程序执行结果 929 18. 解:设f(bt,x,h)返回二叉树bt中x结点的层次,其中h表示bt所指结点的层 930 次,初始调用时,bt指向根结点,h置为1。其递归模型如下: 931 f(bt,x,h)=0 当bt=NULL 932 f(bt,x,h)=h 当bt≠NULL且bt->data=x 933 f(bt,x,h) =l 当l=f(bt->lchild,x,h+1)≠0 934 f(bt,x,h) =f(bt->rchild,x,h+1) 其他情况 935 对应的递归程序如下: 936 #include "Btree.cpp" //包含二叉树的基本运算算法 937 int Level(BTNode *bt,int x,int h)//求二叉树bt中x结点的层次 938 { //初始调用时:bt为根,h为1 939if (bt==NULL) return 0; 940if (bt->data==x) //找到x结点,返回h 941 return h; 942else 943{ int l=Level(bt->lchild,x,h+1); //在左子树中查找 944 if (l!=0)//在左子树中找到,返回其层次l 945return l; 946 else 947return Level(bt->rchild,x,h+1);//返回在右子树的查找结果 948} 949 } 950 void main() 951 { BTNode *bt; 952Int a[]={5,2,3,4,1,6}; 953Int b[]={2,3,5,1,4,6}; 954int n=sizeof(a)/sizeof(a[0]); 955bt=CreateBTree(a,b,n);//由a和b构造二叉链bt 956printf("二叉树bt:"); DispBTree(bt); printf("\n"); 957int x=1; 958printf("%d结点的层次: %d\n",x,Level(bt,x,1)); 959DestroyBTree(bt); //销毁树bt 960 } 961 上述程序的执行结果如图1.20所示。 962 963 964 965 966 967 图1.20程序执行结果 968 20  969 第1章概论 1.3 第3章─分治法 970 971 1.3.1练习题 972 1. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分 973 别解决子问题,最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 974 ( )。 975 A.问题规模相同,问题性质相同 976 B.问题规模相同,问题性质不同 977 C.问题规模不同,问题性质相同 978 D.问题规模不同,问题性质不同 979 2. 在寻找n个元素中第k小元素问题中,如快速排序算法思想,运用分治算法对n 980 个元素进行划分,如何选择划分基准?下面( )答案解释最合理。 981 A.随机选择一个元素作为划分基准 982 B.取子序列的第一个元素作为划分基准 983 C.用中位数的中位数方法寻找划分基准 984 D.以上皆可行。但不同方法,算法复杂度上界可能不同 985 3. 对于下列二分查找算法,以下正确的是( )。 986 A. 987 int binarySearch(int a[], int n, int x) 988 { int low=0, high=n-1; 989while(lowa[mid]) low=mid; 993else high=mid; 994} 995return –1; 996 } 997 B. 998 int binarySearch(int a[], int n, int x) 999 { int low=0, high=n-1;1000while(low+1!=high)1001{ int mid=(low+high)/2;1002 if(x>=a[mid]) low=mid;1003else high=mid;1004}1005if(x==a[low]) return low;1006else return –1;1007 }1008 C.1009 int binarySearch (int a[], int n, int x)1010 { int low=0, high=n-1;1011while(low= a[0])1027{ int low = 0, high = n-1;1028 while(low lchild),f(bt->rchild)}+1其他情况1174 对应的程序如下:1175 #include "Btree.cpp" //包含二叉树的基本运算算法int Height(BTNode *bt) //求二叉树bt的高度1176 { if (bt==NULL) return 0;1177int lh=Height(bt->lchild); //子问题11178int rh=Height(bt->rchild); //子问题21179if (lh>rh) return lh+1;//合并1180else return rh+1;1181 }1182 void main()1183 { BTNode *bt;1184Int a[]={5,2,3,4,1,6};1185Int b[]={2,3,5,1,4,6};1186int n=sizeof(a)/sizeof(a[0]);1187bt=CreateBTree(a,b,n);//由a和b构造二叉链bt1188printf("二叉树bt:"); DispBTree(bt); printf("\n");1189printf("bt的高度: %d\n",Height(bt));1190DestroyBTree(bt); //销毁树bt1191 }1192 1193 25  1194 1195 1196 1197 上述程序的执行结果如图1.23所示。11981199 1200 算法设计 1201 1202 1203 1204 1205 1206 图1.23程序执行结果1207 13. 解:设f(bt)返回二叉树bt中度为2的结点个数,对应的递归模型如下:1208 f(bt)=0 当bt=NULL1209 f(bt)=f(bt->lchild)+f(bt->rchild)+1若bt≠NULL且bt为双分支结点1210 f(bt)=f(bt->lchild)+f(bt->rchild) 其他情况1211 对应的算法如下:1212 #include "Btree.cpp"//包含二叉树的基本运算算法1213 int Nodes(BTNode *bt)//求bt中度为2的结点个数1214 { int n=0;1215if (bt==NULL) return 0;1216if (bt->lchild!=NULL && bt->rchild!=NULL)1217 n=1;1218return Nodes(bt->lchild)+Nodes(bt->rchild)+n;1219 }1220 void main()1221 { BTNode *bt;1222Int a[]={5,2,3,4,1,6};1223Int b[]={2,3,5,1,4,6};1224int n=sizeof(a)/sizeof(a[0]);1225bt=CreateBTree(a,b,n); //由a和b构造二叉链bt1226printf("二叉树bt:"); DispBTree(bt); printf("\n");1227printf("bt中度为2的结点个数: %d\n",Nodes(bt));1228DestroyBTree(bt);//销毁树bt1229 }1230 上述程序的执行结果如图1.24所示。1231 1232 1233 1234 1235 1236 图1.24程序执行结果1237 14. 解:设f(bt,x)返回在二叉排序树bt得到的值为x结点的地址,若没有找到返回 1238 空,对应的递归模型如下:1239 f(bt,x)=NULL当bt=NULL1240 f(bt,x)=bt 当bt≠NULL且x=bt->data1241 f(bt,x)=f(bt->lchild,x)当x>bt->data1242 1243 26  1244 第1章概论 1245 f(bt,x)=f(bt->rchild,x)当xdata1246 对应的程序如下:1247 #include "Btree.cpp"//包含二叉树的基本运算算法1248 BTNode *Search(BTNode *bt,Int x)//在二叉排序树bt查找的值为x结点{ if (bt==NULL) return NULL;1249if (x==bt->data) return bt;1250if (xdata) return Search(bt->lchild,x);1251else return Search(bt->rchild,x);1252 }1253 void main()1254 { BTNode *bt;1255Int a[]={4,3,2,8,6,7,9};1256Int b[]={2,3,4,6,7,8,9};1257int n=sizeof(a)/sizeof(a[0]);1258bt=CreateBTree(a,b,n); //构造一棵二叉排序树bt1259printf("二叉排序树bt:"); DispBTree(bt); printf("\n");1260int x=6;1261BTNode *p=Search(bt,x);1262if (p!=NULL)1263 printf("找到结点: %d\n",p->data);1264else1265 printf("没有找到结点\n",x);1266DestroyBTree(bt);//销毁树bt1267 }1268 上述程序的执行结果如图1.25所示。1269 1270 1271 1272 1273 1274 图1.25程序执行结果1275 Search(bt,x)算法采用的是减治法,最好的情况是某个结点左右子树高度大致相同, 1276 其平均执行时间T(n)如下:1277 T(n)=1 当n=11278 T(n)=T(n/2)+1当n>11279 可以推出T(n)=O(log2n),其中n为二叉排序树的结点个数。1280 15. 解:采用二分查找方法。a[i]=i时表示该元素在有序非重复序列a中恰好第i大。 1281 对于序列a[low..high],mid=(low+high)/2,若a[mid]=mid表示找到该元素;若a[mid]>mid 说明右区间的所有元素都大于其位置,只能在左区间中查找;若a[mid]1)个整数元素的a,所有元素不相同,采用蛮力法求出a中所 有元素的全排列。1481 1.4.2练习题参考答案1482 1. 答:蛮力法是一种简单直接地解决问题的方法,适用范围广,是能解决几乎所有 问题的一般性方法,常用于一些非常基本、但又十分重要的算法(排序、查找、矩阵乘法 和字符串匹配等),蛮力法主要解决一些规模小或价值低的问题,可以作为同样问题的更 1483 高效算法的一个标准。而分治法采用分而治之思路,把一个复杂的问题分成两个或更多的 相同或相似的子问题,再把子问题分成更小的子问题直到问题解决。分治法在求解问题 1484 时,通常性能比蛮力法好。1485 2. 答:如果用蛮力法求解的问题可以分解为若干个规模较小的相似子问题,此时可 以采用递归来实现算法。1486 3. 解:上述算法的时间复杂度为O(n2),采用的是最基本的蛮力法。可以先对a中元 素递增排序,然后依次比较相邻元素的差,求出最小差,改进后的算法如下:1487 #include 1488 #include 1489 using namespace std;1490 int Mindif1(int a[],int n)1491 { sort(a,a+n);//递增排序1492int dmin=a[1]-a[0];1493for (int i=2;i0)1643 35  1644 1645 算法设计1646 1647{ sum+=n%10;1648 n=n/10;1649}1650return sum;1651 }1652 bool solve(int n)//判断n是否为Smitch数1653 { int m=2;1654int sum1=Sum(n);1655int sum2=0;1656while (n>=m)1657{ if (n%m==0) //找到一个质因数m1658 { n=n/m;1659sum2+=Sum(m);1660 }1661 else1662m++;1663}1664if (sum1==sum2)1665 return true;1666else1667 return false;1668 }1669 void main()1670 { int n;1671while (true)1672{ scanf("%d",&n);1673 if (n==0) break;1674 while (!solve(n))1675n++;1676 printf("%d\n",n);1677}1678 }1679 10. 解:采用蛮力法,统计每一列相邻相同颜色的棋格个数countj,在countj中求最 大值。对应的程序如下:1680 #include 1681 #define MAXN 511682 //问题表示1683 int n;1684 char board[MAXN][MAXN];1685 int getMaxArea() //蛮力法求解算法1686 { int maxArea=0;1687for (int j=0; j=n)//找到一个叶子结点1885{ if (tw==W)//找到一个满足条件的解,输出它1886count++;1887}1888else //尚未找完1889{ rw-=w[i]; //求剩余的集装箱重量和1890 if (tw+w[i]=W)//右孩子结点剪枝:剪除不可能存在解的结点1893dfs(tw,rw,i+1);//不选取第i个集装箱,回溯1894}1895 }1896 bool solve()//判断简单装载问题是否存在解1897 1898 40  1899 第1章概论 1900 1901 { count=0;1902int rw=0;1903for (int j=0;j0)1906 return true;1907else1908 return false;1909 }1910 void main()1911 { printf("求解结果\n");1912W=4;1913printf("W=%d时%s\n",W,(solve()?"存在解":"没有解")); W=10;1914printf("W=%d时%s\n",W,(solve()?"存在解":"没有解")); W=12;1915printf("W=%d时%s\n",W,(solve()?"存在解":"没有解")); W=21;1916printf("W=%d时%s\n",W,(solve()?"存在解":"没有解"));}1917 本程序执行结果如图1.35所示。1918 1919 1920 1921 1922 1923 1924 图1.35程序执行结果1925 10. 解:这是一个典型的解空间为子集树的问题,采用子集树的回溯算法框架。当找 1926 到一个解后通过选取的元素个数进行比较求最优解minpath。对应的完整程序如下:1927 #include 1928 #include 1929 using namespace std;1930 //问题表示1931 int a[]={1,2,3,4,5};//设置为全局变量1932 int n=5,k=9;1933 vector minpath;//存放最优解1934 //求解结果表示1935 int minn=n;//最多选择n个元素1936 void disppath() //输出一个解1937 { printf("选择的元素:");1938for (int j=0;ji)1977{ for(int k=i;km 2024 时达到一个叶子结点,输出一个排列。为了避免重复,用used数组实现,used[i]=0表示 没有选择整数i,used[i]=1表示已经选择整数i。对应的完整程序如下:2025 #include 2026 #include 2027 #define MAXN 202028 #define MAXM 102029 int m,n;2030 int x[MAXM]; //x[1..m]存放一个排列2031 bool used[MAXN];2032 void dfs(int i)//求n个元素中m个元素的全排列2033 { if (i>m)2034{ for (int j=1;j0时循环:为x[i]找到一个合适的顶点, 当i=n-1时,若顶点x[i]到顶点v有边对应一个解;否则继续查找下一个顶点。如果不能 为x[i]找到一个合适的顶点,则回溯。采用非递归回溯框架(与《教程》中求解n皇后问 题的非递归回溯框架类似)的完整程序如下:2128 #include 2129 #define MAXV 102130 2131 45  2132 2133 算法设计2134 2135 //求解问题表示2136 int n=5;//图中顶点个数2137 int a[MAXV][MAXV]={{0,1,1,1,0},{1,0,0,1,1},{1,0,0,0,1},{1,1,0,0,1},{0,1,1,1,0}}; //邻接矩阵数组2138 //求解结果表示2139 int x[MAXV];2140 int count;2141 void dispasolution() //输出一个解路径2142 { for (int i=0;i4时,把n分拆成若干个互不相等的自然数的和,分解数的个数越多乘积越 2632 大。为此让n的分解数个数尽可能多(体现贪心的思路),把n分解成从2开始的连续的 自然数之和。例如,分解n为a[0]=2,a[1]=3,a[2]=4,…,a[k]=k+2(共有k+1个分解 2633 数),用m表示剩下数,这样的分解直到m≤a[k]为止,即m≤k+2。对剩下数m的处理分 为如下两种情况:2634 ① m=0;i--)2775{ if(A[i]=0)2776 { ans++;//不满足条件,增加一个会议室2777j--;2778 }2779}2780 }2781 void main()2782 { solve();2783printf("%d\n",ans); //输出22784 }2785 12. 解:与《教程》例7.2类似,会场对应蓄栏,只是这里仅仅求会场个数,即最大 兼容活动子集的个数。对应的完整程序如下:2786 #include 2787 #include 2788 #include 2789 using namespace std;2790 #define MAX 512791 //问题表示2792 struct Action //活动的类型声明2793 2794 59  2795 2796 算法设计2797 2798 { int b; //活动起始时间2799int e; //活动结束时间2800bool operator s ? s : minRow;2854minRow = a[minRow][j+1] == a[i][j+1] && minRow > i ? i : minRow;2855minRow = a[minRow][j+1] == a[x][j+1] && minRow > x ? x : minRow;2856return a[minRow][j+1];2857 }2858 void solve()2859 { int i,j,min;2860for (j=n-2; j>=0; j--)2861 for (i=0; i2时2908 可以采用如下递归算法求解:2909 long f(int n)2910 { if (n==1) return 1;2911if (n==2) return 2;2912long sum=1;2913for (int i=1;i0表示f(i)已经求出,直接返回dp[i]即可,这样避免了重复计算。对应 的算法如下:2961 long dp[MAX];//dp[n]保存f(n)的计算结果2962 long f1(int n)2963 { if (n==1)2964{ dp[n]=1;2965 return dp[n];2966}2967if (n==2)2968{ dp[n]=2;2969 return dp[n];2970 63  2971 2972 算法设计2973 2974}2975if (dp[n]>0) return dp[n];2976long sum=1;2977for (int i=1;i0 时表示对应的f(i)已经求出,直接返回就可以了。对应的完整程序如下:2983 #include 2984 #include 2985 #define MAXN 2012986 //问题表示2987 int n;2988 int a[MAXN];2989 int fa(int i)//求a[i]2990 { int ans=1;2991if (a[i]>0)2992 return a[i];2993for(int j=1;j03041 最后结果是dp[m][n]。对应的程序如下:3042 #include 3043 #include 3044 #define MAXX 513045 #define MAXY 513046 //问题表示3047 int m,n;3048 //求解结果表示3049 int dp[MAXX][MAXY];3050 void solve()3051 { int i,j;3052dp[0][0]=0;3053memset(dp,0,sizeof(dp));3054for (i=1;i(y)?(x):(y))3079 #define MAX 51//序列中最多的字符个数3080 //问题表示3081 int m,n;3082 string arr1,arr2;3083 //求解结果表示3084 int dp[MAX][MAX];//动态规划数组3085 vector subs;//存放LCS3086 void LCSlength()//求dp3087 { int i,j;3088for (i=0;i> arr2;//输入arr1和arr23114m=arr1.length(); //m为arr1的长度3115n=arr2.length(); //n为arr2的长度3116LCSlength();//求出dp3117Buildsubs();//求出LCS3118cout (y)?(x):(y))3246 #define MAX 51//序列中最多的字符个数3247 //问题表示3248 int m,n;3249 string arr1,arr2;3250 //求解结果表示3251 int dp[MAX][MAX];//动态规划数组3252 vector subs;//存放LCS3253 void LCSlength()//求dp3254 { int i,j;3255for (i=0;i> arr2;//输入arr1和arr23284m=arr1.length(); //m为arr1的长度3285n=arr2.length(); //n为arr2的长度3286LCSlength();//求出dp3287Buildsubs();//求出LCS3288cout adjlist[v].firstarc;3581for (i=0;in;i++) dist[i]=INF;3582while (p!=NULL)3583{ w=p->adjvex;3584 3585 74  3586 第1章概论 3587 3588 dist[w]=p->weight; //距离初始化3589 e.i=w; e.v=dist[w];//将v的出边顶点进队qu3590 qu.push(e);3591 p=p->nextarc;3592}3593S[v]=1;//源点编号v放入S中3594for (i=0;in-1;i++) //循环直到所有顶点的最短路径都求出3595{ e=qu.top(); qu.pop();//出队e3596 u=e.i; //选取具有最小最短路径长度的顶点u3597 S[u]=1; //顶点u加入S中3598 p=G->adjlist[u].firstarc;3599 while (p!=NULL) //考察从顶点u出发的所有相邻点3600 { w=p->adjvex;3601if (S[w]==0) //考虑修改不在S中的顶点w的最短路径长度if (dist[u]+p->weightweight; //修改最短路径长度3603e.i=w; e.v=dist[w];3604qu.push(e); //修改最短路径长度的顶点进队3605 }3606p=p->nextarc;3607 }3608}3609 }3610 void Disppathlength(int v,int dist[]) //输出最短路径长度3611 { printf("从%d顶点出发的最短路径长度如下:\n",v);3612for (int i=0;in;++i)3613 if (i!=v)3614printf("到顶点%d: %d\n",i,dist[i]);3615 }3616 void main()3617 { int A[MAXV][MAXV]={3618 {0,4,6,6,INF,INF,INF},3619 {INF,0,1,INF,7,INF,INF},3620 {INF,INF,0,INF,6,4,INF},3621 {INF,INF,2,0,INF,5,INF},3622 {INF,INF,INF,INF,0,INF,6},3623 {INF,INF,INF,INF,1,0,8},3624 {INF,INF,INF,INF,INF,INF,0}};3625int n=7, e=12;3626CreateAdj(G,A,n,e); //建立图的邻接表3627printf("图G的邻接表:\n");3628DispAdj(G); //输出邻接表3629int v=0;3630int dist[MAXV];3631Dijkstra(v,dist);//调用Dijkstra算法3632Disppathlength(v,dist);//输出结果3633DestroyAdj(G);//销毁图的邻接表3634 }3635 上述程序的执行结果如图1.49所示。3636 3637 75  3638 3639 算法设计3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 图1.49 程序执行结果3653 其中Dijkstra算法的时间复杂度为O(n(log2e+MAX(顶点的出度)),一般图中最大顶点 3654 出度远小于e,所以进一步简化时间复杂度为O(nlog2e)。3655 11. 有一个带权有向图G(所有权为正整数),采用邻接矩阵存储。设计一个算法求 3656 其中的一个最小环。3657 解:利用Floyd算法求出所有顶点对之间的最短路径,若顶点i到j有最短路径,而 3658 图中又存在顶点j到i的边,则构成一个环,在所有环中比较找到一个最小环并输出。对 应的程序如下:3659 #include "Graph.cpp" //包含图的基本运算算法3660 #include 3661 using namespace std;3662 void Dispapath(int path[][MAXV],int i,int j)3663 //输出顶点i到j的一条最短路径3664 { vector apath; //存放一条最短路径中间顶点(反向) 3665int k=path[i][j];3666apath.push_back(j);//路径上添加终点3667while (k!=-1 && k!=i)//路径上添加中间点3668{ apath.push_back(k);3669 k=path[i][k];3670}3671apath.push_back(i);//路径上添加起点3672for (int s=apath.size()-1;s>=0;s--) //输出路径上的中间顶点3673 printf("%d→",apath[s]);3674 }3675 int Mincycle(MGraph g,int A[MAXV][MAXV],int &mini,int &minj)3676 //在图g和A中的查找一个最小环3677 { int i,j,min=INF;3678for (i=0;i0,对应的面积(p2-p1)?(p3-p1)/2为正。3823 当三角形p1-p2-p3顺时针方向时,如图1.53所示,p2-p1在p3-p1的逆时针方向上, 3824 (p2-p1)?(p3-p1)0 && area2>0 && area3>0)3881 return true;3882else3883 return false;3884 }3885 void main()3886 { printf("求解结果\n");3887Point p1(0,0);3888Point p2(5,-4);3889Point p3(4,3);3890Point p4(3,1);3891Point p5(-1,1);3892printf("p1:"); p1.disp(); printf("\n");3893printf("p2:"); p2.disp(); printf("\n");3894printf("p3:"); p3.disp(); printf("\n");3895printf("p4:"); p4.disp(); printf("\n");3896 3897 80  3898 第1章概论 3899 3900printf("p5:"); p5.disp(); printf("\n");3901printf("p1p2p3三角形面积: %g\n",getArea(p1,p2,p3));3902printf("p4在p1p2p3三角形内部: %s\n",Intrig(p4,p1,p2,p3)?"是":"不是"); printf("p5在p1p2p3三角形内部: %s\n",Intrig(p5,p1,p2,p3)?"是":"不是");}3903 上述程序的执行结果如图1.55所示。3904 3905 3906 3907 3908 3909 3910 3911 3912 图1.55 程序执行结果3913 1.11 第11章─计算复杂性理论3914 3915 1.11.1 练习题3916 1. 旅行商问题是NP问题吗?3917 A.否B.是C.至今尚无定论3918 2. 下面有关P问题,NP问题和NPC问题,说法错误的是( )。3919 A.如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属 3920 于P问题3921 B.NP问题是指可以在多项式的时间里验证一个解的问题3922 C.所有的P类问题都是NP问题3923 D.NPC问题不一定是个NP问题,只要保证所有的NP问题都可以约化到它即可3924 3. 对于《教程》例11.2设计的图灵机,分别给出执行f(3,2)和f(2,3)的瞬像演变过 3925 程。3926 4. 什么是P类问题?什么是NP类问题?3927 5. 证明求两个m行n列的二维矩阵相加的问题属于P类问题。3928 6. 证明求含有n个元素的数据序列中求最大元素的问题属于P类问题。3929 7. 设计一个确定性图灵机M,用于计算后继函数S(n)=n+1(n为一个二进制数),并 3930 给出求1010001的后继函数值的瞬像演变过程。3931 1.11.2 练习题参考答案3932 1. 答:B。3933 2. 答:D。3934 3. 答:(1)执行f(3,2)时,输入带上的初始信息为000100B,其瞬像演变过程如 3935 3936 81  3937 3938 3939 3940 下:39413942 3943 算法设计 3944 q0000100B?Bq100100B? B0q10100B?B00q1100B? B001q200B?B00q3110B?3945 B0q30110B?Bq300110B?q3B00110B?Bq000110B?BBq10110B?BB0q1110B?3946 BB01q210B?BB011q20B?BB01q311B?BB0q3111B?BBq30111B?BBq00111B?3947 BBB1q211B?BBB11q21B?BBB111q2B?BBB11q41B?BBB1q41BB?3948 BBBq41BBB?BBBq4BBBB?BBB0q6BBB3949 最终带上有一个0,计算结果为1。3950 (2)执行f(2,3)时,输入带上的初始信息为001000B,其瞬像演变过程如下:3951 q0001000B?Bq001000B?B0q11000B?B01q2000B?B0q31100B?Bq301100B?3952 q3 B01100B?Bq001100B?BBq11100B?BB1q2100B?BB11q200B?BB1q3100B?3953 BBq31100B?Bq3B1100B?BBq01100B?BBBq5100B?BBBBq500B?3954 BBBBBq50B?BBBBBBq5B?BBBBBBBq63955 最终带上有零个0,计算结果为0。3956 4. 答:用确定性图灵机以多项式时间界可解的问题称为P类问题。用非确定性图灵 3957 机以多项式时间界可解的问题称为NP类问题。3958 5. 答:求两个m行n列的二维矩阵相加的问题对应的算法时间复杂度为O(mn),所 3959 以属于P类问题。3960 6. 答:求含有n个元素的数据序列中最大元素的问题的算法时间复杂度为O(n),所 3961 以属于P类问题。3962 7. 解: q0为初始状态,q3为终止状态,读写头初始时注视最右边的格。δ动作函数 3963 如下:3964 δ(q0,0)→(q1,1,L)3965 δ(q0,1)→(q2,0,L)3966 δ(q0,B)→(q3,B,R)3967 δ(q1,0)→(q1,0,L)3968 δ(q1,1)→(q1,1,L)3969 δ(q1,B)→(q3,B,L)3970 δ(q2,0)→(q1,1,L)3971 δ(q2,1)→(q2,0,L)3972 δ(q2,B)→(q3,B,L)3973 求10100010的后继函数值的瞬像演变过程如下:3974 B1010001q00B?B101000q111B?B10100q1011B?B1010q10011B?B101q100011B3975 ?B10q1100011B?B1q10100011B?Bq110100011B?q1B10100011B3976 ?q3BB10100011B3977 其结果为10100011。3978 3979 3980 3981 3982 3983 82  3984 第1章概论 3985 1.12第12章─概率算法和近似算法3986 3987 1.12.1练习题3988 1. 蒙特卡罗算法是( )的一种。3989 A.分枝限界算法B.贪心算法C.概率算法 D.回溯算法3990 2. 在下列算法中有时找不到问题解的是( )。3991 A.蒙特卡罗算法B.拉斯维加斯算法C.舍伍德算法D.数值概率算法3992 3. 在下列算法中得到的解未必正确的是( )。3993 A.蒙特卡罗算法B.拉斯维加斯算法C.舍伍德算法D.数值概率算法3994 4. 总能求得非数值问题的一个解,且所求得的解总是正确的是( )。3995 A.蒙特卡罗算法B.拉斯维加斯算法C.数值概率算法 D.舍伍德算法3996 5. 目前可以采用( )在多项式级时间内求出旅行商问题的一个近似最优解。3997 A.回溯法B.蛮力法C.近似算法D.都不可能3998 6. 下列叙述错误的是()。3999 A.概率算法的期望执行时间是指反复解同一个输入实例所花的平均执行时间4000 B.概率算法的平均期望时间是指所有输入实例上的平均期望执行时间4001 C.概率算法的最坏期望事件是指最坏输入实例上的期望执行时间4002 D.概率算法的期望执行时间是指所有输入实例上的所花的平均执行时间4003 7. 下列叙述错误的是()。4004 A.数值概率算法一般是求数值计算问题的近似解4005 B.Monte Carlo总能求得问题的一个解,但该解未必正确4006 C.Las Vegas算法的一定能求出问题的正确解4007 D.Sherwood算法的主要作用是减少或是消除好的和坏的实例之间的差别4008 8. 近似算法和贪心法有什么不同?4009 9. 给定能随机生成整数1到5的函数rand5(),写出能随机生成整数1到7的函数 4010 rand7()。4011 1.12.2练习题参考答案4012 1. 答:C。4013 2. 答:B。4014 3. 答:A。4015 4. 答:D。4016 5. 答:C。4017 6. 答:对概率算法通常讨论平均的期望时间和最坏的期望时间,前者指所有输入实 4018 例上平均的期望执行时间,后者指最坏的输入实例上的期望执行时间。答案为D。4019 7. 答:一旦用拉斯维加斯算法找到一个解,那么这个解肯定是正确的,但有时用拉 4020 斯维加斯算法可能找不到解。答案为C。4021 8. 答:近似算法不能保证得到最优解。贪心算法不一定是近似算法,如果可以证明 4022 4023 83  4024 4025 算法设计4026 4027 决策既不受之前决策的影响,也不影响后续决策,则贪心算法就是确定的最优解算法。4028 9. 解:通过rand5()*5+rand5()产生6,7,8,9,…,26,27,28,29,30这25个整 4029 数,每个整数x出现的概率相等,取前面3*7=21个整数,舍弃后面的4个整数,将{6, 7,8}转化成1,{9,10,11}转化成2,以此类推,即由y= (x-3)/3为最终结果。对应的程 序如下:4030 #include 4031 #include //包含产生随机数的库函数4032 #include 4033 int rand5()//产生一个[1,5]的随机数4034 { int a=1,b=5;4035return rand()%(b-a+1)+a;4036 }4037 int rand7()//产生一个[1,7]的随机数4038 { int x;4039do4040{4041 x=rand5()*5+rand5();4042} while (x>26);4043int y=(x-3)/3;4044return y;4045 }4046 void main()4047 { srand((unsigned)time(NULL)); //随机种子4048for (int i=1;i
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多