鱼C论坛

 找回密码
 立即注册
查看: 3085|回复: 1

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

[复制链接]
发表于 2017-7-15 16:38:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

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 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-7-15 17:48:19 | 显示全部楼层
@人造人 帮忙评分
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 16:11

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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