算法设计作业

作业"/>

算法设计作业

7-8 python

def quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)# 测试代码
n = int(input())
arr = []
for i in range(n):x = int(input())arr.append(x)
arr = quicksort(arr)
for index,a in enumerate(arr):if index == len(arr) - 1:print(f'{a}')breakprint(f'{a}', end=' ')

7-9 c++

#include<stdio.h>
#include<stdlib.h>
int a[110];
int n;
void merge(int a[],int tem[],int p,int q,int r)
{int i=p;int j=q+1;int pos=p;while(i<=q&&j<=r){if(a[i]<a[j])tem[pos++]=a[i++];elsetem[pos++]=a[j++];}while(i<=q) tem[pos++]=a[i++];while(j<=r) tem[pos++]=a[j++];while(p<=r){a[p]=tem[p];p++;}
}void print(int s[],int n){int t=0;for(t=0;t<n;t++){printf("%d",s[t]);if(t==n-1){printf("\n");}else{printf(" ");}}    
}void msort(int a[],int tem[],int p,int r){if(p<r){int q=(p+r)/2;msort(a,tem,p,q);msort(a,tem,q+1,r);merge(a,tem,p,q,r);print(a,n);}
}void merge_sort(int a[],int n)
{int tem[n];msort(a,tem,0,n-1);}int main()
{int i=0;while(~scanf("%d",&n)){for(i=0;i<n;i++)scanf("%d",&a[i]);merge_sort(a,n);}return 0;
}

7-10 c++

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> m >> n;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i++) {for (int j = m; j >= v[i]; j--) {f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;
}

7-11 python

def matrix_chain_order(p):n = len(p) - 1 m = [[0 for x in range(n + 1)] for y in range(n + 1)]for L in range(2, n + 1):for i in range(1, n - L + 2):j = i + L - 1m[i][j] = float('inf')for k in range(i, j):q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]if q < m[i][j]:m[i][j] = qreturn m[1][n]if __name__ == "__main__":n = int(input())dims = list(map(int, input().split()))print(matrix_chain_order(dims))

7-12 c++

#include <iostream>
#include <string>
#include <stack>
using namespace std;
void LCS(string s1,string s2)
{int m=s1.length()+1;int n=s2.length()+1;int **c;int **b;c=new int* [m];b=new int* [m];for(int i=0;i<m;i++){c[i]=new int [n];b[i]=new int [n];for(int j=0;j<n;j++)b[i][j]=0;}for(int i=0;i<m;i++)c[i][0]=0;for(int i=0;i<n;i++)c[0][i]=0;for(int i=0;i<m-1;i++){for(int j=0;j<n-1;j++){if(s1[i]==s2[j]){c[i+1][j+1]=c[i][j]+1;b[i+1][j+1]=1;          //1表示箭头为  左上}else if(c[i][j+1]>=c[i+1][j]){c[i+1][j+1]=c[i][j+1];b[i+1][j+1]=2;          //2表示箭头向  上}else{c[i+1][j+1]=c[i+1][j];b[i+1][j+1]=3;          //3表示箭头向  左}}}stack<char> same;                   //存LCS字符stack<int> same1,same2;             //存LCS字符在字符串1和字符串2中对应的下标，方便显示出来for(int i = m-1,j = n-1;i >= 0 && j >= 0; ){if(b[i][j] == 1){i--;j--;same.push(s1[i]);same1.push(i);same2.push(j);}else if(b[i][j] == 2)i--;elsej--;}for(int i=0;i<m && !same1.empty();i++)      //输出字符串1的标记{if(i==same1.top()){same1.pop();}elsecontinue;}for(int i=0;i<n && !same2.empty();i++)      //输出字符串2的标记{if(i==same2.top()){same2.pop();}elsecontinue;}cout<<"LCS("<<s1<<","<<s2<<")=";while(!same.empty()){cout<<same.top();same.pop();}
}
int main()
{string s1;cin>>s1;string s2;cin>>s2;LCS(s1,s2);return 0;
}