2.1 insertion sort 《算法导论》答案
本帖最后由 超凡天赐 于 2017-7-15 17:38 编辑http://osghw5zsd.bkt.clouddn.com/屏幕快照 2017-07-15 上午10.22.13.png
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={1,2,3,4,5,6,7,8,9,10};
for(i=1;i<=9;i++)
{
right_hand=card;
j=i-1;
while(j>=0&&card<right_hand)
{
card=card;
j--;
}
card=right_hand;
}
for(i=0;i<10;i++)
printf("%d ",card);
return 0;
}
[*]升序
#include <stdio.h>
int main()
{
int i,j,right_hand;
int card={10,9,8,7,6,5,4,3,2,1};
for(i=1;i<=9;i++)
{
right_hand=card;
j=i-1;
while(j>=0&&card>right_hand)
{
card=card;
j--;
}
card=right_hand;
}
for(i=0;i<10;i++)
printf("%d ",card);
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==v)
return i;
return NIL;
}
int main()
{
int p={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（0<=j<=i-1），但v有可能等于a（i<=j<=n）。这个0<=j<=i-1非常关键，如果我们写成了0<=j<=i这一题有可能就证不出来了。
[*]initialization：当i=0时，我们会发现我们需要证明的v不会出现在a~a[-1]之中，但有可能出现在a~a之中。a~a[-1]明显是个空集，v怎么可能会出现在空集之中，所以这里初始化正确。
[*]maintenance：我们进行一次迭代。我们来分类讨论：1.如果v=a[ i ],函数就会被立刻返回i。不过这个仍然满足循环不变式。2.如果v!=a[ i ],会进行i会自加一次，仍然符合循环不变式。
[*]termination：当我们进行最后一次迭代时，i=n+1时，v仍不在a~a之中，所以仍符合循环不变式。但此时会返回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);
printf("please input the second binary integer\n");
for(i=0;i<n;i++)
scanf("%d",&b);
for(i=n;i>=1;i--)
{
temp=a+b+temp1;
if(temp>=2)
{
c=a+b-2+temp1;
temp1=1;
}
else
{
c=a+b+temp1;
temp1=0;
}
}
if(temp1==1)
c=1;
else
c=0;
for(i=0;i<=n;i++)
printf("%d",c);
printf("\n");
return 0;
}
算法思想就是普通的二进制加法，逢二进一。 @人造人 帮忙评分{:10_281:}
页:
[1]