|
|
################################
|
|
|
|
|
|
#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)
|
|
|
//对应例2.8的算法由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链
|
|
|
{
|
|
|
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++) //在b中查找b[k]=root的根结点
|
|
|
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)
|
|
|
//采用括号表示输出二叉链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)
|
|
|
//释放以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; //bt结点加入apath
|
|
|
if (bt->lchild == NULL && bt->rchild == NULL) //bt结点为叶结点
|
|
|
{
|
|
|
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);
|
|
|
}
|
|
|
|
|
|
|
|
|
##############################
|
|
|
|
|
|
#include <stdio.h>
|
|
|
//求解结果表示
|
|
|
int num; //全局变量,存放众数
|
|
|
int maxcnt = 0; //全局变量,存放重数
|
|
|
void split(int a[], int low, int high, int& mid, int& left, int& right)
|
|
|
//以a[low..high]中间的元素为界限,确定为等于a[mid]元素的左、右位置left和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) //a[low..high]序列至少有1个元素
|
|
|
{
|
|
|
int mid, left, right;
|
|
|
split(a, low, high, mid, left, right);
|
|
|
int cnt = right - left + 1; //求出a[mid]元素的重数
|
|
|
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);
|
|
|
}
|
|
|
####################################
|
|
|
|
|
|
#include <iostream>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N=1010;
|
|
|
int v[N],w[N],f[N];
|
|
|
int n,m;
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
scanf("%d%d",&n,&m);
|
|
|
|
|
|
for(int i=1;i<=n;i++) scanf("%d%d",&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]);
|
|
|
}
|
|
|
|
|
|
printf("%d",f[m]);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
######################################
|
|
|
|
|
|
#include<stdio.h>
|
|
|
int Fibon1(int n)
|
|
|
{
|
|
|
if (n == 1 || n == 2)
|
|
|
{
|
|
|
return 1;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
return Fibon1(n - 1) + Fibon1(n - 2);
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int n = 0;
|
|
|
int ret = 0;
|
|
|
scanf("%d", &n);
|
|
|
ret = Fibon1(n);
|
|
|
printf("ret=%d", ret);
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int Fibno2(int n)
|
|
|
{
|
|
|
int num1 = 1;
|
|
|
int num2 = 1;
|
|
|
int tmp = 0;
|
|
|
int i = 0;
|
|
|
if (n < 3)
|
|
|
{
|
|
|
return 1;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
for (i = 0; i>n-3; i++)
|
|
|
{
|
|
|
tmp = num1 + num2;
|
|
|
num1 = num2;
|
|
|
num2 = tmp;
|
|
|
}
|
|
|
return tmp;
|
|
|
}
|
|
|
}
|
