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

// test5.2.cpp : 定义控制台应用程序的入口点。 // // 2010.5.9 //sylar // #include "stdafx.h" #include 
   
     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 
    
      >weight[i]; cout<<"输入第"< 
     
       >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<<"最大价值为"< 
      
        "< 
       
         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 
        
          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) 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 
          
            #include 
           
             #include 
            
              #include 
             
               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< 
              
                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 
               
                 t) { j--; } if (i 
                
                  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 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< 
                  
                    node_value; pre_order(root->left); pre_order(root->right); } //先序遍历一个二叉树，非递归实现 void pre_order_ex1(pbtree root) { xj_stack 
                   
                     m_stack; while (root != NULL || m_stack.is_empty() != 1) { if (root != NULL) { cout< 
                    
                      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< 
                     
                       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