|
|
### 01-01
|
|
|
|
|
|
~~~c
|
|
|
#include<stdio.h>
|
|
|
#define max(x,y)((x)>(y)?(x):(y))
|
|
|
#define MAXN 20
|
|
|
int n = 5,W = 10;
|
|
|
int w[MAXN] = {0,2,4,5,6};
|
|
|
int v[MAXN] = {0,2,2,3,5};
|
|
|
int maxv = 0;
|
|
|
int knap(int i,int r){
|
|
|
if(i==0||r==0){
|
|
|
return 0;
|
|
|
}
|
|
|
if(r<w[i]){
|
|
|
knap(i-1,r);
|
|
|
} else{
|
|
|
return max(knap(i-1,r),knap(i-1,r-w[i])+v[i]);
|
|
|
}
|
|
|
}
|
|
|
int main(){
|
|
|
maxv = knap(n,W);
|
|
|
printf("求解的最优结果(最优方案)\n");
|
|
|
printf("选取的物品：");
|
|
|
int x[MAXN] = {0};
|
|
|
int i=n,r = W;
|
|
|
while(i>=0&&r>0){
|
|
|
if(i>0&&knap(i,r)!=knap(i-1,r)){
|
|
|
x[i]=1;
|
|
|
r = r-w[i];
|
|
|
}
|
|
|
i--;
|
|
|
}
|
|
|
for(i=1;i<=n;i++){
|
|
|
if(x[i]==1){
|
|
|
printf("%d ",i);
|
|
|
}
|
|
|
}
|
|
|
printf("\n");
|
|
|
printf("总价值=%d",maxv);
|
|
|
}
|
|
|
~~~
|
|
|
|
|
|
### 02-01
|
|
|
|
|
|
~~~c
|
|
|
#include<stdio.h>
|
|
|
int fib(int n){
|
|
|
if(n<=2){
|
|
|
return n;
|
|
|
}else{
|
|
|
return fib(n-1)+fib(n-2);
|
|
|
}
|
|
|
}
|
|
|
int main(){
|
|
|
int n;
|
|
|
printf("请输入想打印的斐波拉契数列：\n");
|
|
|
scanf("%d",&n);
|
|
|
printf("斐波那契数列：\n");
|
|
|
for(int i = 0;i<=n;i++){
|
|
|
printf("%d ",fib(i));
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
~~~
|
|
|
|
|
|
### 03-01
|
|
|
|
|
|
~~~c
|
|
|
#include<stdio.h>
|
|
|
typedef struct{
|
|
|
int number;
|
|
|
int count;
|
|
|
} Mode;
|
|
|
Mode findMode(int arr[],int n){
|
|
|
Mode mode = {arr[0],1};
|
|
|
int count = 1;
|
|
|
int maxCount = 1;
|
|
|
for(int i=0;i<n;i++){
|
|
|
if(arr[i] == arr[i-1]){
|
|
|
count++;
|
|
|
}else{
|
|
|
if(count>maxCount){
|
|
|
mode.number = arr[i-1];
|
|
|
mode.count = count;
|
|
|
maxCount = count;
|
|
|
}
|
|
|
count = 1;
|
|
|
}
|
|
|
}
|
|
|
if(count>maxCount){
|
|
|
mode.number = arr[n-1];
|
|
|
mode.count = count;
|
|
|
}
|
|
|
return mode;
|
|
|
}
|
|
|
int main(){
|
|
|
int arr[] = {1,2,2,2,3,3,5,6,6,6,6};
|
|
|
int n = sizeof(arr)/sizeof(arr[0]);
|
|
|
printf("递增序列: ");
|
|
|
for (int i = 0; i < n; i++)//输出待求众数序列中的元素；
|
|
|
printf("%d ",arr[i]);
|
|
|
printf("\n");
|
|
|
Mode result = findMode(arr,n);
|
|
|
printf("众数为：%d,重数为：%d",result.number,result.count);
|
|
|
return 0;
|
|
|
}
|
|
|
~~~
|
|
|
|
|
|
### 03-02
|
|
|
|
|
|
~~~c
|
|
|
#include <stdio.h>
|
|
|
int num;
|
|
|
int maxcnt = 0;
|
|
|
void split(int a[], int low, int high, int& mid, int& left, int& right)
|
|
|
{
|
|
|
mid = (low + high) / 2;
|
|
|
for (left = low; left <= high; left++)
|
|
|
if (a[left] == a[mid])
|
|
|
break;
|
|
|
for (right = left + 1; right <= high; right++)
|
|
|
if (a[right] != a[mid])
|
|
|
break;
|
|
|
right--;
|
|
|
}
|
|
|
void Getmaxcnt(int a[], int low, int high)
|
|
|
{
|
|
|
if (low <= high)
|
|
|
{
|
|
|
int mid, left, right;
|
|
|
split(a, low, high, mid, left, right);
|
|
|
int cnt = right - left + 1;
|
|
|
if (cnt > maxcnt)
|
|
|
{
|
|
|
num = a[mid];
|
|
|
maxcnt = cnt;
|
|
|
}
|
|
|
Getmaxcnt(a, low, left - 1);
|
|
|
Getmaxcnt(a, right + 1, high);
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[] = {1,2,2,2,3,3,5,6,6,6,6};
|
|
|
int n = sizeof(a) / sizeof(a[0]);
|
|
|
printf("求解结果\n");
|
|
|
printf(" 递增序列: ");
|
|
|
for (int i = 0; i < n; i++)//输出待求众数序列中的元素；
|
|
|
printf("%d ",a[i]);
|
|
|
printf("\n");
|
|
|
Getmaxcnt(a, 0, n - 1);
|
|
|
printf(" 众数: %d, 重数: %d\n", num, maxcnt);
|
|
|
}
|
|
|
|
|
|
|
|
|
~~~
|
|
|
|
|
|
|
|
|
|
|
|
### 04-01
|
|
|
|
|
|
~~~c
|
|
|
#include<stdio.h>
|
|
|
#include<stdlib.h>
|
|
|
#define max(a,b)((a)>(b)?(a):(b))
|
|
|
typedef struct TreeNode{
|
|
|
int val;
|
|
|
struct TreeNode *left;
|
|
|
struct TreeNode *right;
|
|
|
}TreeNode;
|
|
|
int maxPathHelper(TreeNode *root,int *maxSum){
|
|
|
if(root==NULL){
|
|
|
return 0;
|
|
|
}
|
|
|
int leftSum = maxPathHelper(root->left,maxSum);
|
|
|
int rightSum = maxPathHelper(root->right,maxSum);
|
|
|
int currSum = max(max(root->val,root->val+leftSum+rightSum),
|
|
|
max(root->val+leftSum,root->val+rightSum));
|
|
|
*maxSum = max(*maxSum,currSum);
|
|
|
return max(root->val,max(root->val+rightSum,root->val+leftSum));
|
|
|
}
|
|
|
int maxPathSum(TreeNode *root){
|
|
|
if(root==NULL){
|
|
|
return 0;
|
|
|
}
|
|
|
int maxSum = 0;
|
|
|
maxPathHelper(root,&maxSum);
|
|
|
return maxSum;
|
|
|
}
|
|
|
TreeNode* createTreeNode(int val){
|
|
|
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
|
|
|
newNode->val=val;
|
|
|
newNode->left=NULL;
|
|
|
newNode->right=NULL;
|
|
|
return newNode;
|
|
|
}
|
|
|
int main(){
|
|
|
TreeNode* root = createTreeNode(-10);
|
|
|
root->left=createTreeNode(9);
|
|
|
root->right=createTreeNode(20);
|
|
|
root->right->left=createTreeNode(15);
|
|
|
root->right->right=createTreeNode(7);
|
|
|
int maxSum = maxPathSum(root);
|
|
|
printf("最大的路径和为：%d",maxSum);
|
|
|
free(root->left);
|
|
|
free(root->right);
|
|
|
free(root);
|
|
|
return 0;
|
|
|
}
|
|
|
~~~
|
|
|
### 04-02
|
|
|
|
|
|
~~~c
|
|
|
#include <vector>
|
|
|
#include <string>
|
|
|
#include<stdlib.h>
|
|
|
using namespace std;
|
|
|
typedef int ElemType;
|
|
|
typedef struct node
|
|
|
{
|
|
|
ElemType data;
|
|
|
struct node* lchild;
|
|
|
struct node* rchild;
|
|
|
} BTNode;
|
|
|
BTNode* CreateBTree(ElemType a[], ElemType b[], int n)
|
|
|
{
|
|
|
int k;
|
|
|
if (n <= 0) return NULL;
|
|
|
ElemType root = a[0];
|
|
|
BTNode* bt = (BTNode*)malloc(sizeof(BTNode));
|
|
|
bt->data = root;
|
|
|
for (k = 0; k < n; k++)
|
|
|
if (b[k] == root)
|
|
|
break;
|
|
|
bt->lchild = CreateBTree(a + 1, b, k);
|
|
|
bt->rchild = CreateBTree(a + k + 1, b + k + 1, n - k - 1);
|
|
|
return bt;
|
|
|
}
|
|
|
void DispBTree(BTNode* bt)
|
|
|
{
|
|
|
if (bt != NULL)
|
|
|
{
|
|
|
printf("%d", bt->data);
|
|
|
if (bt->lchild != NULL || bt->rchild != NULL)
|
|
|
{
|
|
|
printf("(");
|
|
|
DispBTree(bt->lchild);
|
|
|
if (bt->rchild != NULL) printf(",");
|
|
|
DispBTree(bt->rchild);
|
|
|
printf(")");
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
void DestroyBTree(BTNode*& bt)
|
|
|
{
|
|
|
if (bt != NULL)
|
|
|
{
|
|
|
DestroyBTree(bt->lchild);
|
|
|
DestroyBTree(bt->rchild);
|
|
|
free(bt);
|
|
|
}
|
|
|
}
|
|
|
int maxsum = 0;
|
|
|
vector<int> maxpath;
|
|
|
void Findmaxpath(BTNode* bt, vector <int > apath, int asum)
|
|
|
{
|
|
|
if (bt == NULL)
|
|
|
return;
|
|
|
apath.push_back(bt->data); asum += bt->data;
|
|
|
asum += bt->data;
|
|
|
if (bt->lchild == NULL && bt->rchild == NULL)
|
|
|
{
|
|
|
if (asum - maxsum)
|
|
|
{
|
|
|
maxsum = asum;
|
|
|
maxpath.clear();
|
|
|
maxpath = apath;
|
|
|
}
|
|
|
}
|
|
|
Findmaxpath(bt->lchild, apath, asum);
|
|
|
Findmaxpath(bt->rchild, apath, asum);
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
BTNode* bt;
|
|
|
ElemType a[] = { 5,2,3,4,1,6 };
|
|
|
ElemType b[] = { 2,3,5,1,4,6 };
|
|
|
int n = sizeof(a)/sizeof(a[0]);
|
|
|
bt = CreateBTree(a,b,n);
|
|
|
printf("实验结果:\n");
|
|
|
printf("二叉树bt:");
|
|
|
DispBTree(bt);
|
|
|
printf("'in");
|
|
|
printf("最大路径");
|
|
|
vector<int> apath;
|
|
|
int asum = 0;
|
|
|
Findmaxpath(bt,apath,asum);
|
|
|
printf("路径和: % d，路径 : ",maxsum);
|
|
|
for (int i=0;i < maxpath.size();i++)
|
|
|
printf("%d ",maxpath[i]);
|
|
|
printf("\n");
|
|
|
printf("销毁树bt\n");
|
|
|
DestroyBTree(bt);
|
|
|
}
|
|
|
~~~
|
|
|
|
