已知了最小费用流和最小割的性质，写写最大流的各种变体。 READ MORE →
图论：最小费用流与Bellman-Ford算法
最小传输费用问题
稀疏矩阵转置之快速转置法
数据结构作业题目 = =
前情回顾：矩阵转置-简单代码
一个简单的约瑟夫环代码
动态链表的课后作业。直接上代码：
READ MORE →
矩阵转置-简单代码
利用数组对两个矩阵进行转置。附上简单代码：
READ MORE →
区间调度问题
题目描述：
有n项工作，每项工作分别在si时间开始，ti时间结束。对于每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。
你的目标是参与尽可能多的工作，那么你最多能参与多少项工作呢？
限制条件：
1<=n<=100000
1<=si<=ti,=10^9
这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。
比较容易想到的算法如：
- 在可选工作中，每次选取最先开始的工作
- 在可选工作中，每次选取用时最短的工作
- 在可选工作中，每次选取与最少可选工作有重叠的工作
- 在可选工作中，每次选取结束时间最早的工作
而很显然，前三项算法都不具有普适性（例如：一项开头早，持续时间长的工作和两项开头晚的工作）。
关于最后一种算法的解释：
结束时间早，对应的可选工作就越多。当然也可以用归纳法来证明。
代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <stdio.h> #include <tchar.h> #include <queue> using namespace std; const int N = 5; int s[N]={1,2,4,6,8}; int t[N]={3,5,7,9,10}; int solve() { pair<int, int> itv[N]; for(int i = 0; i < N; i ++) { itv[i].first = s[i]; itv[i].second = t[i]; } sort(itv, itv + N); int count = 0; int t = 0; for(int i = 0; i < N; i ++) { if(t < itv[i].first) { count ++; t = itv[i].second; } } return count; } int main() { cout << solve() << endl; return 0; } |
栈
栈是支持push和pop的数据结构。
push是在栈的顶端放入一组数据；pop是在栈的顶端取出一组数据。
Last in first out(LIFO):最后进入栈的一组数据会被最先取出.
样例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include #include using namespace std; int main() { stack s;//声明int类型数据存储的栈 s.push(1);//『』→『1』 s.push(2);//『1』→『1,2』 s.push(3);//『1,2』→『1,2,3』 printf("%dn",s.top());//3 s.pop();//栈顶移除3，下同 printf("%dn",s.top()); s.pop(); printf("%dn",s.pop()); s.pop();//『1』→『』 return 0; } |
返回栈顶元素：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// test_stack.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <stack> #include <vector> #include <deque> #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { stack<int> mystack; mystack.push(10); mystack.push(20); mystack.top()-=5; cout << "mystack.top() is now " << mystack.top() << endl; return 0; } |
哈夫曼编码
已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
综合训练：试编写一个将百分制分数转换为五级分制的程序。要求其时间性能尽可能好（即平均比较次数尽可能少）。假设学生成绩的分布情况如下：
分数 0-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.40 0.30 0.10
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
#include<stdio.h> #include<stdlib.h> #include<string.h> #define ERROR 0 #define OK 1 typedef int Status; typedef struct {//声明哈夫曼树的结点 int weight; int parent; int lchild; int rchild; }Htnode,*Huffmantree; typedef char ** Huffmancode;//相当于声明一个二维数组，来记录每个权值对应的编码。 void Select (Huffmantree &HT,int t,int &p,int &q);//选择结点中权值最小的两个结点，用p,q来返回。 void creathuffmantree(Huffmantree &HT,Huffmancode &HC,int *w,int n)//创建哈夫曼树。 { int m,i,p,q,j,start,s; if(n<=1) return; m=2*n-1;//当n大于1时，就需要2*n-1个结点 HT=(Huffmantree)malloc(sizeof(Htnode)*(m+1));//因为0不存东西，而从1开始存，所以申请m+1个空间。 for(i=1;i<=n;i++)//对叶子结点进行初始化，除权之外全赋值为0。 { HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].rchild=0; HT[i].lchild=0; } for(i=n+1;i<=m;i++)//对非叶子结点进行初始化，所有的值全为0 { HT[i].weight=0; HT[i].parent=0; HT[i].rchild=0; HT[i].lchild=0; } for(i=n+1;i<=m;i++)//这是创建树的主要步骤，找出权值和最小的两棵树，再把它们合并成一棵树，依次进行，知道走后还剩仅有的一棵树。 { Select(HT,i-1,p,q);//这是选择权值最小的两棵树的函数，并用p,q来返回，在上面已经声明过。 HT[i].weight=HT[p].weight+HT[q].weight;//对刚合并的新树的根结点的权值进行赋值。 HT[i].lchild=p;//新树的左孩子赋为p; HT[i].rchild=q;//新树的右孩子赋为q; HT[p].parent=i;//把他们的双亲都赋为i; HT[q].parent=i; } HC=(Huffmancode)malloc(sizeof(char*)*(n+1));//申请一个大小为n+1的存放指针的数组。 char* cd=(char*)malloc(sizeof(char)*n);//申请一个一维数组，作为一个中转站，最后把他复制到HC中的一个数组中。 for(i=1;i<=n;i++)//对哈夫曼树的数组从1到n进行依次遍历，这是从叶子结点到根节点。 { start=n-1;//对这个一位数组进行倒着存，最后正着读取。 cd[start]=' '; s=i; while(HT[s].parent!=0) { j=s; s=HT[s].parent; if(HT[s].lchild==j)//如果该结点是双亲结点的左孩子，应该把它赋为0； cd[--start]='0'; if(HT[s].rchild==j)//如果该结点是双亲结点的右孩子，应该把它赋为1； cd[--start]='1'; } HC[i]=(char *)malloc(sizeof(char)*(n-start)); strcpy(HC[i],&cd[start]);//把cd数组里的内容复制到HC[i]里，再用cd去盛其他的编码。 } free(cd);//最后可以把cd数组给释放了。 } void Select (Huffmantree & HT,int t,int &min1,int &min2)//选择结点中权值最小的两个结点，用p,q来返回。 { int i=1,flag=0; while(flag<2)//这个while循环是为了找出前两棵树的根结点，把他们当成最小的两棵树，以后来做比较，求出最小的两个。 { if(HT[i].parent!=0)//如果不是根结点，继续朝后找，直到找到根结点。 i++; else//如果是根结点，就把他们分别赋给min1和min2. { if(flag==0) min1=i; else min2=i; flag++; i++; } } if(HT[min1].weight>HT[min2].weight)//对min1和min2进行比较，把最小的的付给min1,第二小的付给min2. { t=min1; min1=min2; min2=t; } while(i<=t)//把以后的各个结点的权值与最小的两个比较，调整下，最后得出的就是最小的两个结点。 { if(HT[i].parent!=0)//如果不是根结点，继续朝后找，直到找到根结点。 i++; else { if(HT[i].weight<=HT[min1].weight)//如果该结点的权值比最小的结点还小，把最小的两个全重新赋值。 { min2=min1; min1=i; } else if(HT[i].weight>=HT[min1].weight&&HT[i].weight<=HT[min2].weight)//如果该结点的权值在最小和第二小之间的话， //就把第二小的重新赋值。 min2=i; i++; } } } Status exhuffmantree(Huffmantree &HT,int m,char *code,int *ex,int &j)//这是解码的函数，m为那棵树的根结点，code是输入的哈夫曼码， //解码后最后给他存到ex数组中，j为数组的长度。 { int i=0,k=m; while(code[i]!=' ')//从根结点到叶子节点去匹配，输出最后的那个权值 { if(code[i]=='0'&&HT[k].lchild!=0)//如果code[i]是0,并且左孩子不为0，则继续朝叶子结点找。 { k=HT[k].lchild; i++; } else if(code[i]=='1'&&HT[k].rchild!=0)//如果code[i]是1,并且右孩子不为0，则继续朝叶子结点找。 { k=HT[k].rchild; i++; } else if(HT[k].rchild==0&&HT[k].lchild==0)//如果是叶子结点，则把它的权值赋给ex[j]. { ex[j]=HT[k].weight; j++; k=m; } else//其他的则返回ERROR。 return ERROR; } if(HT[k].rchild==0&&HT[k].lchild==0)//当跳出循环的时候，说明应该到了叶子结点，如果是叶子结点，则把它的权值赋给ex[j]. { ex[j]=HT[k].weight; return OK; } else//其他的则返回ERROR。 return ERROR; } int main() { Huffmantree HT; Huffmancode HC; char Code[100]; int i, n,a[100],b[100],j=0,t; printf("输入叶子结点的个数n为：n"); scanf("%d",&n); printf("依次输入n个叶子结点的权值为：n"); for(i=0;i<n;i++) scanf("%d",&a[i]); creathuffmantree(HT,HC,a,n); printf("输出该哈夫曼树各个叶子结点的编码为：n"); for(i=1;i<=n;i++) { t=0; while(HC[i][t]!=' ') { printf("%c",HC[i][t]); t++; } putchar(' '); } putchar('n'); getchar(); printf("输入该哈夫曼树关联的要译码的code数组：n"); gets(Code); exhuffmantree(HT,2*n-1,Code,b,j); printf("输出解码后的各权值为：n"); for(i=0;i<=j;i++) printf("%d ",b[i]); putchar('n'); return 0; } |
快速幂取余算法例题
问题描述:
求 B ^ P % M = ?
代码实现:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <cstdio> using namespace std; int main() { freopen("input.txt","r",stdin); int B,P,M; while (~scanf("%d%d%d",&B,&P,&M)) { int ans = 1; B = B % M; while (P > 0) { if (P%2) ans = ans * B % M; P /= 2; B = (B*B) % M; } printf("%dn",ans); } } |
辗转相除法
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。
例题：