2.1 insertion sort 《算法导论》答案

超凡天赐

                               
登录/注册后可看大图

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语言代码来写，以后也用：

• 降序
  

  #include <stdio.h>
  int main()
  {
      int i,j,right_hand;
      int card[10]={1,2,3,4,5,6,7,8,9,10};
      for(i=1;i<=9;i++)
      {
          right_hand=card[i];
          j=i-1;
          while(j>=0&&card[j]<right_hand)
          {
              card[j+1]=card[j];
              j--;
          }
          card[j+1]=right_hand;
      }
      for(i=0;i<10;i++)
          printf("%d ",card[i]);
      return 0;
  }

• 升序

  #include <stdio.h>
  int main()
  {
      int i,j,right_hand;
      int card[10]={10,9,8,7,6,5,4,3,2,1};
      for(i=1;i<=9;i++)
      {
          right_hand=card[i];
          j=i-1;
          while(j>=0&&card[j]>right_hand)
          {
              card[j+1]=card[j];
              j--;
          }
          card[j+1]=right_hand;
      }
      for(i=0;i<10;i++)
          printf("%d ",card[i]);
      return 0;
  }

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在这里可以理解为简单的一个一个找。写出代码为：

#include <stdio.h>
#define NIL -1
int linear_search(int v,int *a)
{
    int i;
    for(i=0;i<=9;i++)
        if(a[i]==v)
            return i;
    return NIL;
}
int main()
{
    int p[10]={1,2,3,4,5,6,7,8,9,10};
    int result;
    int v;
    scanf("%d",&v);
    result=linear_search(v, p);
    printf("%d",result);
    return 0;
}

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

• Stack Overflow上的答案
• 谷歌上搜到的答案1
• 谷歌上搜到的答案2
  

现在我自己来写一下：

• 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.

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,i,temp,temp1=0;
    printf("please input how much bit is number\n");
    scanf("%d",&n);
    int *a,*b,*c;
    a=malloc(n*sizeof(int));
    b=malloc(n*sizeof(int));
    c=malloc((n+1)*sizeof(int));
    printf("please input the first binary integer\n");//输入时，数字之间要加上空格。
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    printf("please input the second binary integer\n");
    for(i=0;i<n;i++)
        scanf("%d",&b[i]);
    for(i=n;i>=1;i--)
    {
        temp=a[i-1]+b[i-1]+temp1;
        if(temp>=2)
        {
            c[i]=a[i-1]+b[i-1]-2+temp1;
            temp1=1;
        }
        else
        {
            c[i]=a[i-1]+b[i-1]+temp1;
            temp1=0;
        }
    }
    if(temp1==1)
        c[0]=1;
    else
        c[0]=0;
    for(i=0;i<=n;i++)
        printf("%d",c[i]);
    printf("\n");
    return 0;
}

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

超凡天赐

@人造人 帮忙评分