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

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

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

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

img

简单插入排序

#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]);
    }
}

img

选择排序

#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]);
    }
}

img

冒泡排序

#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]);
    }
}

img

背包问题

//一维数组解法
#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
*/

img


#include <stdio.h>
#include <stdlib.h>

//打印输出
void show(int *a,int N) {
    for (int i = 0; i < N; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");

}

void bubble_sort(int *a,int len) {
    printf("**********冒泡排序**********\n");
    int temp, i, j;
    for (i = 0; i < len-1; i++) {
        for (j = 0; j < len - i - 1; j++)
            if (a[j] > a[j + 1]) {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;

            }
        show(a,len);
    }

}

void select_sort(int *a,int len) {
    printf("**********选择排序**********\n");
    int temp, i, j,index;
    for(i=0; i<len-1; i++) {
        index=i;
        for(j=i+1; j<len; j++)
            if(a[j]<a[index])
                index=j;//index存放最小值所在的下标
        temp=a[index];//最小元素与下标为k的元素交换
        a[index]=a[i];
        a[i]=temp;
        show(a,len);
    }

}

void insert_sort(int *a,int len) {
    printf("**********插入排序**********\n");
    int i,j,temp;
    for (i=1; i<len; i++) {
        temp=a[i];
        //前一个数大于当前数则交换位置
        for (j = i; j > 0 && a[j-1]>temp; j--) {
            a[j]=a[j-1];
        }
        a[j]=temp;
        show(a,len);
    }
}

int main() {
    //冒泡排序
    int arr1[]= {43, 4, 79, 22};
    int len1=sizeof(arr1)/sizeof(int);
    bubble_sort(arr1,len1);

    //选择排序
    int arr2[]= {43, 4, 79, 22};
    int len2=sizeof(arr2)/sizeof(int);
    select_sort(arr2,len2);
    //插入排序
    int arr3[]= {43, 4, 79, 22};
    int len3=sizeof(arr3)/sizeof(int);
    insert_sort(arr3,len3);
    return 0;
}

img