01-01

#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

#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

#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

#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

#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

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