大学计算机—计算思维导论 习题求解

Question

1. 按三种不同的内排序算法对下列数据完成排序：43, 4, 79, 22。
   

（1）插入法排序，要求写出每次插入一个数据后的数据排列状态；
（2）简单选择法排序，要求写出每次选择一个元素并安置到合适位置后的数据排列状态；
（3）冒泡法排序，要求写出每个轮次的数据排列结果。

1. 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量
   内，我们如何选择，才能使得物品的总价格最高。下图是背包问题的一个例子，应该选择哪
   些盒子，才能使价格尽可能地大，并且保持总重量不超过 15 kg？所选物品的总价值是多少？

Answer 1

简单插入排序

#include"stdio.h"
void displayArray(int*a,int n){
    int i;
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
// 直接插入排序:默认排序结果是非递减有序序列
void directInsertSort(int*a,int length){
    int tmp,i, j;
    displayArray(a,length);
    for(i=1;i<length;i++){
        if(a[i]<a[i-1]){
            tmp=a[i];
            for(j=i-1;j>=0&&a[j]>tmp;j--){
                a[j+1]=a[j];
            }
            a[j+1]=tmp;
        }
        displayArray(a,length);
    }
}
int main(){
    int a[]={43,4,79,22};
    directInsertSort(a,sizeof(a)/sizeof(int));
    int i,len=sizeof(a)/sizeof(int);
    printf("Result:\n");
    for(i=0;i<len;i++){
        printf("%d ",a[i]);
    }
}

选择排序

#include"stdio.h"
void displayArray(int*a,int n){
    int i;
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
void swap(int*a,int*b){(*a)^=(*b);(*b)^=(*a);(*a)^=(*b);}
void selectSort(int a[],int len){
    int minpos=0,i,j;
    displayArray(a,len);
    for(i=0;i<len-1;i++){
        minpos=i;
        for(j=i+1;j<len;j++){
            if(a[j]<a[minpos]) minpos=j;
        }
        if(minpos!=i){
            swap(&a[i],&a[minpos]);
        }
        displayArray(a,len);
    }
}
int main(){
    int a[]={43,4,79,22};
    int len = sizeof(a)/sizeof(int);
    selectSort(a,len);
    int i;
    printf("Result:\n");
    for(i=0;i<len;i++){
        printf("%d ",a[i]);
    }
}

冒泡排序

#include"stdio.h"
void displayArray(int*a,int n){
    int i;
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
void swap(int*a,int*b){ (*a)^=(*b);(*b)^=(*a);(*a)^=(*b);}
//线性排序的冒泡排序:递增序列
void bubbleSort(int a[],int len){
    int flag;
    displayArray(a,len);
    for(int i=len-1;i>0;i--) {
        flag=0;
        for(int j=0;j<i;j++){
            if(a[j]>a[j+1]){//将大的后移
                flag=1;
                swap(&a[j],&a[j+1]);
            }
        }
        if(!flag) break;
        displayArray(a,len);
    }  
}
int main(){
    int a[]={43,4,79,22};
    int len = sizeof(a)/sizeof(int);
    bubbleSort(a,len);
    printf("Result:\n");
    for(int i=0;i<len;i++){
        printf("%d ",a[i]);
    }
}

背包问题

//一维数组解法
#include<stdio.h>
#define MAX_M 12880        //最大限重
#define MAX_N 3402        // 最大种类数
#define max(a,b) a>b?a:b

int dp[MAX_M + 1]={0};
int weights[MAX_N + 1];
int values[MAX_N + 1];

int main() {
    int n, m, i, j;
    scanf("%d%d", &n , &m);//n是种类，m是限制重量
    for (i = 1; i <= n; i++) {
        scanf("%d%d", &weights[i] ,&values[i]);
    }
    for (i = 1; i <= n; i++) {
        for (j = m; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    printf("%d\n", dp[m] );
}
/*
5 15
4 12
2 2
2 1
1 1
10 4
*/