QQ登录

只需一步,快速开始

搜索
鱼C论坛笔记大赛成绩公示
查看: 193|回复: 1

[学习笔记] 2.1 insertion sort 《算法导论》答案

[复制链接]
最佳答案
16 
累计签到:173 天
连续签到:3 天
发表于 2017-7-15 16:38:44 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 超凡天赐 于 2017-7-15 17:38 编辑


                               
登录/注册后可看大图


2.1-1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A ={31; 41; 59; 26; 41; 58}
这一题很简单,自己想一想过程。(figure 2.2是升序)

2.1-2

Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.
这一题用c语言代码来写,以后也用:

  • 降序

    1. #include <stdio.h>
    2. int main()
    3. {
    4.     int i,j,right_hand;
    5.     int card[10]={1,2,3,4,5,6,7,8,9,10};
    6.     for(i=1;i<=9;i++)
    7.     {
    8.         right_hand=card[i];
    9.         j=i-1;
    10.         while(j>=0&&card[j]<right_hand)
    11.         {
    12.             card[j+1]=card[j];
    13.             j--;
    14.         }
    15.         card[j+1]=right_hand;
    16.     }
    17.     for(i=0;i<10;i++)
    18.         printf("%d ",card[i]);
    19.     return 0;
    20. }
    复制代码

  • 升序
    1. #include <stdio.h>
    2. int main()
    3. {
    4.     int i,j,right_hand;
    5.     int card[10]={10,9,8,7,6,5,4,3,2,1};
    6.     for(i=1;i<=9;i++)
    7.     {
    8.         right_hand=card[i];
    9.         j=i-1;
    10.         while(j>=0&&card[j]>right_hand)
    11.         {
    12.             card[j+1]=card[j];
    13.             j--;
    14.         }
    15.         card[j+1]=right_hand;
    16.     }
    17.     for(i=0;i<10;i++)
    18.         printf("%d ",card[i]);
    19.     return 0;
    20. }
    复制代码



2.1-3
Consider the searching problem:

Input: A sequence of n numbers A = {a1; a2; : : : ;} and a value.

Output: An index i such that v = A[ i ] or the special value NIL if  does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

这一题并不简单:所谓的linear search在这里可以理解为简单的一个一个找。写出代码为:

  1. #include <stdio.h>
  2. #define NIL -1
  3. int linear_search(int v,int *a)
  4. {
  5.     int i;
  6.     for(i=0;i<=9;i++)
  7.         if(a[i]==v)
  8.             return i;
  9.     return NIL;
  10. }
  11. int main()
  12. {
  13.     int p[10]={1,2,3,4,5,6,7,8,9,10};
  14.     int result;
  15.     int v;
  16.     scanf("%d",&v);
  17.     result=linear_search(v, p);
  18.     printf("%d",result);
  19.     return 0;
  20. }
复制代码


证明:
我在Google找了不少答案,但都不是令人那么满意。最终在Stack Overflow上找到了一个不错的答案。这里我都给大家放上来,以供大家参考,有可能需要科学上网,也需要懂一点点英文。



现在我自己来写一下:
  • loop invariant:v不等于a[j](0<=j<=i-1),但v有可能等于a[j](i<=j<=n)。这个0<=j<=i-1非常关键,如果我们写成了0<=j<=i这一题有可能就证不出来了。
  • initialization:当i=0时,我们会发现我们需要证明的v不会出现在a[0]~a[-1]之中,但有可能出现在a[0]~a[n]之中。a[0]~a[-1]明显是个空集,v怎么可能会出现在空集之中,所以这里初始化正确。
  • maintenance:我们进行一次迭代。我们来分类讨论:1.如果v=a[ i ],函数就会被立刻返回i。不过这个仍然满足循环不变式。2.如果v!=a[ i ],会进行i会自加一次,仍然符合循环不变式。
  • termination:当我们进行最后一次迭代时,i=n+1时,v仍不在a[0]~a[n]之中,所以仍符合循环不变式。但此时会返回NIL。


2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C. State the problem formally and write pseudocode for adding the two integers.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main()
  4. {
  5.     int n,i,temp,temp1=0;
  6.     printf("please input how much bit is number\n");
  7.     scanf("%d",&n);
  8.     int *a,*b,*c;
  9.     a=malloc(n*sizeof(int));
  10.     b=malloc(n*sizeof(int));
  11.     c=malloc((n+1)*sizeof(int));
  12.     printf("please input the first binary integer\n");//输入时,数字之间要加上空格。
  13.     for(i=0;i<n;i++)
  14.         scanf("%d",&a[i]);
  15.     printf("please input the second binary integer\n");
  16.     for(i=0;i<n;i++)
  17.         scanf("%d",&b[i]);
  18.     for(i=n;i>=1;i--)
  19.     {
  20.         temp=a[i-1]+b[i-1]+temp1;
  21.         if(temp>=2)
  22.         {
  23.             c[i]=a[i-1]+b[i-1]-2+temp1;
  24.             temp1=1;
  25.         }
  26.         else
  27.         {
  28.             c[i]=a[i-1]+b[i-1]+temp1;
  29.             temp1=0;
  30.         }
  31.     }
  32.     if(temp1==1)
  33.         c[0]=1;
  34.     else
  35.         c[0]=0;
  36.     for(i=0;i<=n;i++)
  37.         printf("%d",c[i]);
  38.     printf("\n");
  39.     return 0;
  40. }
复制代码


算法思想就是普通的二进制加法,逢二进一。

评分

参与人数 2荣誉 +13 鱼币 +13 贡献 +5 收起 理由
人造人 + 5 + 5 + 5 热爱鱼C^_^
小甲鱼 + 8 + 8 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
16 
累计签到:173 天
连续签到:3 天
 楼主| 发表于 2017-7-15 17:48:19 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-9-25 12:31 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表