一些简单常用算法整理学习

// test5.2.cpp : 定义控制台应用程序的入口点。
//
// 2010.5.9
//sylar
//
#include "stdafx.h"
#include <iostream>   
using namespace std;   

//动态规划：0-1背包问题   
//bestValue[i][j]=max ( bestValue[i+1][j-w[i]]+v[i] ,bestValue[i+1][j] )  w[i]<=j   
//bestValue[i][j]=bestValue[i+1][j]        w[i]>j   

class Knapsack   
{   
private:   
	int *weight;//物品重量数组   
	int *value;//物品价值数组   
	int numOfItems;//物品数量   
	int bagSpace;//背包容量   
	int **bestValue;//动态规划表格，记录bestValue[i][j]的价值，为最优价值，i表示物品i...n装入容量为j的背包能达到的最大价值   
	int **path;//为了求出取得最优值时的解，记录动态规划表不同表项的选择与否   
public:   
	//构造函数   
	Knapsack(int numOfItems,int bagSpace)   
	{   
		weight=new int[numOfItems+1];   
		value=new int[numOfItems+1];   
		this->bagSpace=bagSpace;   
		this->numOfItems=numOfItems;   

		bestValue=new int* [numOfItems+1];   
		for(int i=0;i<numOfItems+1;i++)   
		{   
			bestValue[i]=new int[bagSpace+1];   
		}   

		path=new int* [numOfItems+1];   
		for(int i=0;i<numOfItems+1;i++)   
		{   
			path[i]=new int[bagSpace+1];   
		}      
	}   
	//输入物品的重量与价值   
	void input()   
	{   
		int i=1;   
		while(i<=numOfItems)   
		{   
			cout<<"输入第"<<i<<"个物品的重量"<<endl;   
			cin>>weight[i];   
			cout<<"输入第"<<i<<"个物品的价值"<<endl;   
			cin>>value[i];   
			++i;   
		}   
	}   
	//动态规划核心算法   
	void knapsack()   
	{   
		//初始化递归最底层,即将bestValue[n][0:c]进行初始化   
		for(int i=0;i<=bagSpace;i++)   
		{   
			if(weight[numOfItems]<=i)   
			{   
				bestValue[numOfItems][i]=value[numOfItems];   
				path[numOfItems][i]=1;   
			}   
			else  
			{   
				bestValue[numOfItems][i]=0;   
				path[numOfItems][i]=0;   
			}   
		}   
		//递推的进行动态规划，自底向上，最终bestValue[1][bageSpace]为1-n物品放入容量bagSpace内的最大价值   
		for(int k=numOfItems-1;k>=1;k--)   
		{   
			for(int j=0;j<=bagSpace;j++)   
			{   
				bestValue[k][j]=bestValue[k+1][j];   
				path[k][j]=0;//不放入的情况   
				if(weight[k]<=j)//如果容量足够放入当前物品   
				{   
					if(bestValue[k+1][j-weight[k]]+value[k]>bestValue[k][j])//如果放入的价值大于不放的价值   
					{   
						bestValue[k][j]=bestValue[k+1][j-weight[k]]+value[k];   
						path[k][j]=1;//那么就选择放入   
					}   
				}   
			}   
		}   
	}   
	//输出最大价值，并且输出选择方式   
	void display()   
	{   
		//打印出bestValue[1][bagSpace],表示1...numOfItems的物品装入容量为bagSpace的最大价值   
		int i=1;   
		int j=bagSpace;   
		cout<<"最大价值为"<<bestValue[1][j]<<endl;   
		//根据path[1][bagSpace]的记录开始，递归到path[n][某容量],从而打印出每个物品是否被选择进入背包   
		while(i<=numOfItems)   
		{   
			if(path[i][j]==0)//如果i物品没被放入，看i+1个物品装入容量j背包   
			{   
				++i;   
			}   
			else  
			{   
				cout<<"<重量:"<<weight[i]<<"，价值:"<<value[i]<<">"<<endl;   
				j-=weight[i];   
				++i;   
			}   
		}   
	}   
};   

/*
void main()   
{   
	Knapsack test(5,50);//5个物品，背包容量50   
	test.input();//输入5个物品的价值与重量   
	test.knapsack();//动态规划   
	test.display();//打印选择与最大价值   
}  
*/


//动态规划：0-1背包问题
//bestValue[i][j]=max ( bestValue[i+1][j-w[i]]+v[i] ,bestValue[i+1][j] )  w[i]<=j
//bestValue[i][j]=bestValue[i+1][j]        w[i]>j


/*
思路总结： 看到一个题目，首先看问什么，下面以此题举例分析一下。

0-1背包问题

1，问题要求什么？  
答：求把n个物品放入容量C的背包内能达到的最大价值

2，转换成一个抽象一点的数学表达式是什么？  
答：bestValue[n][C]，表示n个物品放入容量C的背包的最大价值

3，不考虑算法应该怎么选择，我们实际去解决这个问题的时候，是从哪里开始去做的？
答：我们有n个物品，C容量背包。  于是我们开始解决问题，我先放第一个物品，如果能放进去，我就放进去，当然，我也可以不放。
第一个物品处理结束以后，我们着手于第二个物品，能放进去就放进去，当然，我们也可以不放。  
所以，这就是一个决策问题，决策是从我们实际处理问题中抽象出来的，我们放物品的时候只能一个一个放，决策是放或者不放。

4，在决策了解的情况，我们应该考虑当前要求的bestValue[n][C]，在决策放入或者不放入的情况，分别等于什么?
答：如果能够放入，那么我们的背包还有C-w[i], 物品还有n-1个，当然，我们也可以选择不放进去，那么我们背包依旧有C容量，物品还有n-1个。 所以我们修改一下我们对bestValue[n][C]的定义，从而就得到了一个最优子结构的递归公式。

为了我们决策的进行，即我们每次决策都是最第i个物品进行决策，所以bestValue[n][C]修改为best[i][C],表示i,i+1,i+2...n个物品放入容量为C的背包的最大价值。

所以：bestValue[i][j]=max ( bestValue[i+1][j-w[i]]+v[i] ,bestValue[i+1][j] )  w[i]<=j
bestValue[i][j]=bestValue[i+1][j]        w[i]>j

意思是：
如果当前容量j装不下物品i，那么i到n装入j的最大价值就等于i+1到n装入j的最大价值，就是公式的第二行。
如果当前容量j可以装下物品i，那么我们可以装进去，当然，也可以犯贱，不装进去，看看结果如何，所以i到n个物品装入j容量背包的最大价值就等于 i+1到n物品装入j-w[i]容量的背包可以达到的最大价值+value[i] ，i+1到n物品装入j容量背包的最大价值，这两种不同决策的一个最大值。

总结：解决什么?  从哪里开始做起？  有哪些决策？  决策后会怎么样？ 

找出了递归式，它具有最优子结构性质，即可以简单的理解为：当前的最优产生于子问题的最优，然后子问题的最优不受当前最优的影响，并且通过观察递归公式，应该找到递归的最底层的i,j分别是什么，我们观察到i在逐渐增加，j在逐渐减小，所以我们在递推的时候，首先把最底层进行初始化，然后利用递归公式向上递推。 所以我们需要首先初始化bestValue[n][0:C],即记录第n个物品装入0到C的背包的能达到的价值，当w[n]<=j时，bestValue[n][j]等于value[n]，如果w[n]>j,即容量不够，那么就是0.

我们能够从底向上递推的重要原因就是：最优子结构+无后效性 。 多多体会吧。 这是基础理解了。

*/



#include <stdio.h>
int a[100],n,temp;
void QuickSort(int h,int t)
{
	if(h>=t) return;
	int mid=(h+t)/2,i=h,j=t,x;
	x=a[mid];
	while(1)
	{
		while(a[i]<x) i++;
		while(a[j]>x) j--;
		if(i>=j) break;
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	a[mid]=a[j];
	a[j]=x;
	QuickSort(h,j-1);
	QuickSort(j+1,t);
	return;
}
/*
int main()
{
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&a[i]);
	QuickSort(0,n-1);
	for(i=0;i<n;i++) printf("%d ",a[i]);
	return(0);
}
*/



#include "stdafx.h"
#include<stdio.h> 
#include<math.h> 
#include <string.h>
#include <iostream>
using namespace std;

/*
//伪代码
//
if  等于 ' '
{
直接输出5个
}
else if 不等于' '
{
if 这5个字符串是连续的
{
直接输出这5个字符
}

if 这5个字符中含有' '
{
只输出' '前面的几个字符
}
}
*/

/*
//有一个字符串，由字符和空格组成，输入一个每行最大字符数line_size，则按照每行line_size输出，不够则换行例如
//输入 abcdef ghij kl mn opq  r stxyzuvw  line_size=5
//输出
abcde
f
ghij
kl mn
opq  r
stxyz
uvw
*/


int fun1(char* str, int line_size)
{
	char *p1;
	char* p2;
	int i;
	p1=p2 =str;
	int flag = 0;
	char* out = new char[line_size + 1];
	for (i = 0;  i < strlen(str); i += line_size)
	{
		memset(out, '\0', line_size + 1);
		if ( *(p1 + line_size) == ' ') ///////
		{
			p1 ++;
			strncpy(out, p1, line_size);
			cout << out;
			p1 = p1 + line_size;
			cout<<endl;
		}
		else
		{
			p2 = p1 + line_size;
			while (*(--p2) != ' ' && p2 != p1);
			if (p1 == p2)
			{
				strncpy(out, p1, line_size);
				cout << out;
				p1 = p1 + line_size;
				cout<<endl;
				continue;
			}
			else
			{
				strncpy(out, p1, p2 - p1);
				cout << out;
				p1 = p2;
				cout<<endl;
				continue;
			}
		}
	}
	delete [] out;
	out = NULL;
	return 1;
}

/*
int main()
{
//关键：每5个判断一次，判断位置信息 如果为空，跳过，如果有数字 则计算
char a[1024] = "abcdef ghij kl mn opq r stxyzuvw";
//	fun(a, 5);
fun1(a, 5);
return 1;
}
*/


//输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.编程求解



//3)写出在母串中查找子串出现次数的代码.
int count1(char* str,char* s)
{
	char *src = str;
	char *des = s;
	int times = 0;
	while( *src != '\0')
	{
		if (*src == *des ) 
		{
			char* temp1 = src;
			char* temp2 = des;
			while(  *temp2 != '\0'  && *(temp2++) == *(temp1++)  );
			if(*temp2 == '\0') //如果完全匹配
			{
				times++;      //出现次数加一
				src += strlen(s); 
				continue;
			}
		}
		src++;  //不匹配
	}
	return times;
}

//2)写出二分查找的代码.
int 
bfind(int* a, int len, int val)
{
	int temp;
	int i,j;
	i = 0; j = len - 1;
	//if ()
	while (i <= j)
	{
		temp = (a[i] + a[j])/2;
		if (temp == val)
		{
			return (i + j)/2;
		}
		else if (temp > val)
		{
			j = (i + j)/2 - 1 ;
		}
		else if (temp < val)
		{
			i = (i + j)/2 + 1 ;
		}
	}
	return -1;
}

//快速排序:
void quick_sort(int *x, int low, int high)
{
	int i, j, t;
	if (low < high) 
	{
		i = low;
		j = high;
		t = *(x+low);
		while (i<j) 
		{
			while (i<j && *(x+j)>t) 
			{
				j--; 
			}
			if (i<j) 
			{
				*(x+i) = *(x+j); 
				i++; 
			}
			while (i<j && *(x+i)<=t) 
			{
				i++; 
			}
			if (i<j)
			{
				*(x+j) = *(x+i);
				j--; 
			}
		}
		*(x+i) = t; 
		quick_sort(x,low,i-1); 
		quick_sort(x,i+1,high); 
	}
}
/*
void main()
{
	int temp[] ={3,8,6,2,9,7,1};
	quick_sort(temp, 0, 6);
}
*/

//快速排序:
int partition1(int* a, int begin, int end)
{
	int value;
	int temp;
	int i, j;
	int pos;
	value = a[begin];
	j = end;
	i = begin;
	pos = begin;
	if (begin == end)
	{
		return 1;
	}
	while (i < j)
	{
		while (a[j] > value)  j--;
		while (a[i] < value)  i++;

		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	partition1(a, begin, i);
	partition1(a, i, end);
	return 1;
}

// max1(12, 8);
int max1(int m, int n)
{
	int temp;
	while (m%n != 0)
	{
		temp = n;
		n = m%n;
		m = temp;
	}
	return n;
}

//算法复杂度 m + n
void merge(int a[],int n,int b[],int m,int *c) 
{ 
	int i = 0;
	int j = 0;
	int k = 0;
	while (i < n && j < m)
	{
		if(a[i] < b[j] && i < n)
		{
			c[k] = a[i];
			i++;
		}
		else if(a[i] >= b[j] && j < m)
		{
			c[k] = b[i];
			j++;
		}
		k++;
	}
}

/*
int main()
{

int str1[5] ={1,3,5,7,9};
int str2[5] ={1,2,4,6,8};
int out[30];
merge(str1,5,str2,5,out); 
//	char a[100] = "abcababaabc";
//	/char b[100] = "ab";
//	int num = count1(a, b);

//	int bf[10] =  {1,2,3,4,5,6,7,8,9,10};
//	num = bfind(bf, 10, 10);
int ttt = max1(20, 12);

int a[10] = {4,6,8,1,3,5,7,9,2,10};
partition1(a, 0 , 9);

return 1;
}

*/




//栈（数组栈，指针栈）
//来个简单的数组栈把

template<class T>
class xj_stack
{
public:
	xj_stack()
	{
		memset(array, 0, sizeof(array));
		totol_num = 0;
	}
	T pop_stack()
	{
		if (totol_num == 0)
		{
			return T(1);
		}
		return array[--totol_num];
	}
	int push_stack(T num)
	{
		array[totol_num++] = num;
		return 1;
	}
	int is_empty()
	{
		if (totol_num==0)
		{
			return 1;
		}
		return 0;
	}
protected:
private:
	T array[30];
	int totol_num;
};

typedef struct _btree 
{
	struct _btree * left;
	struct _btree * right;
	int node_value;
}btree, *pbtree;

//建立一个二叉树
//
// 
int create_ntree(pbtree& pnode)
{
	//pbtree pnode;
	int value;
	cin>>value;
	if (value == 0)
	{
		return 0;
	}
	pnode = new btree;
	memset(pnode, '\0', sizeof(btree));
	pnode->node_value = value;
	create_ntree(pnode->left);
	create_ntree(pnode->right);
	return 1;
}

//先序遍历一个二叉树，递归实现
void pre_order(pbtree root)
{
	if (root == NULL)
	{
		return;
	}
	cout<<root->node_value;
	pre_order(root->left);
	pre_order(root->right);
}

//先序遍历一个二叉树，非递归实现
void pre_order_ex1(pbtree root)
{
	xj_stack<pbtree> m_stack;
	while (root != NULL || m_stack.is_empty() != 1)
	{
		if (root != NULL)
		{
			cout<<root->node_value;
			m_stack.push_stack(root);
			root = root->left;
		}
		else
		{
			root = m_stack.pop_stack();
			root = root->right;
		}
	}
}

pbtree root = NULL;
/*
void main()
{
	create_ntree(root);
	pre_order(root);
	cout<<endl;
	pre_order_ex1(root);
}
*/


//寻找第i小的数
#include <iostream>
using namespace std;
const int N=10;
int partition(int *, int,int);
void exchange(int &, int &);

int find_mid_num(int *A, int p, int r, int i){
	if (p==r)
		return A[p];
	int q=partition(A, p, r);
	int k=q-p+1;
	if(k==i)
		return A[q];
	else if(k<i)
		return find_mid_num(A, q+1,r,i-k);
	else
		return find_mid_num(A, p, q-1, i);
}

int partition(int *A, int p, int r){
	int x=A[r];
	int i=p-1;
	for(int j=p;j<r;j++)
		if(A[j]<=x)
		{
			i++;
			exchange(A[j],A[i]);
		}
		exchange(A[i+1],A[r]);
		return i+1;
}

void exchange(int &x, int &y)
{
	int z=x;
	x=y;
	y=z;
}

int main()
{
	int Array[10]={1,4,5,3,8,7,5,9,6,2};
	int m=N/2;
	int output=find_mid_num(Array, 0, N-1, m);
	cout << output << endl;
	while(1);
	return 0;
}