匈牙利解法C程序代码
西安科技大学
程序设计实训报告
班级： ^^^^^^^^^^^
学号： ^^^^^^^^^^
姓名： ^^^^^^
2012年6月20日
题目指派问题的匈牙利法
一、算法思想
本程序根据课本上匈牙利算法思想做了如下操作：首先定义结构体ASS用于存储该矩阵中每个元素，并且定义结构体TrueOrForse用于判断矩阵中每个元素是否被标记。并且定义了相应函数（例如：输出函数）来完成相关操作。
（注释：具体操作见第二步，算法流程与步骤。具体结构体与相关函数祥见源程序首部定义）
二、算法流程与步骤
初始化：
本程序首先根据用户输入转换为其相应的方阵（即行数等于列数）。若人的数量乘以每个人最多工作的任务数量小于或等于任务数量，同时补n行0；否则补n列0。（n 为任务数量减去人的数量乘以每个人最多工作的任务数量的绝对值）。输出该方阵，方便用户检查输入是否正确。
标记：
然后根据用户输入判断是按行减去每行最小值，还是减去每列最小值（注释：若人的数量乘以每个人最多工作的任务数量小于或等于任务数量，则减去每行最小值，否则则减去每列最小值）。然后从中选择其中含0最多的行或列依次进行标记，若所标记的直线数量小于矩阵行数（或列数），则撤销所有标记，选择其中含0最少的行（或列）减去其中除0以外的最小值，并同时将该行出现负数所在列（或行）每个元素加上该负数的相反数。重复以上操作，直到所标记的直线数等于矩阵行数（或列数）。
转换为0-1指派矩阵：
从行与列中选择含零最少的行（或列），将该行（或列）中的零元素先转换为矩阵中不可能出现的一个很大的数，将零出现的行与列进行标记，然后从列（或行）中选择零最少的，并将其中未被标记零元素转化为很大的数，依此类推；直到标记完所有数，最后将很大的数转换为1，其余均转化为0。即得0-1指派矩阵。
三、算法源程序
#include
#include
#include
#include
#include
#define MAXCOUNT 50 // 最大的人数和任务数量
#define TRUE 1
#define FALSE 0
#define INDEF 10000 //指派中不可能出现的数
struct TrueOrForse
{
int marker;
}; //用于记录某元素是否被标记
typedef struct ASS
{
int assign[MAXCOUNT][MAXCOUNT];
struct TrueOrForse sign[MAXCOUNT][MAXCOUNT];
}Assign; //记录指派中各元素，及其是否被标记
void Print(int a[][MAXCOUNT],int Row,int Col); // 输出0-1指派构成的矩阵
void reduceRow(Assign*L,int Row,int Col); // 减去行中最小值
void reduceCol(Assign*L,int Row,int Col); // 减去列中最小值
int CountZero(Assign*L,int Row,int Col,int temp); // 计算其中的零元素，并返回最大（temp 若为0，则返回最小的）的行或列，若都标记完，则返回0
void Zero_marker(Assign*L,int m,int n); // 若m
void SearchAgainByRowReduce(Assign*L,int count,int m); // 搜索未被标记行元素继续操作使其出现0，并将所有数置为正数
void SearchAgainByColReduce(Assign*L,int m,int count); // 搜索未被标记列元素继续操作使其出现0，并将所有数置为正数
void removeMarker(Assign*L,int m); // 撤销所有标记
void ToBest(Assign*L,int count,int m); // 最后化为0-1指派
int main(void)
{
Assign *L = NULL;
int PersonCount = 0,ThingCount = 0; // 人数与任务数量
int OneDoMaxThing = 0; // 一个人最多工作的任务数量
int m; // 记录化成指派问题的行数与列数
int i,j,k;
int flag = 0; // 用于标记本题是人数多，还是任务数量多
int count,count_Count = 0;
int count1[MAXCOUNT] = {0},a[MAXCOUNT] = {0};
L = (Assign*)malloc(sizeof(Assign));
if(L == NULL)
{
printf("存储空间不足。。。");
return 0;
}
memset(L->assign,0,sizeof(int)*MAXCOUNT*MAXCOUNT);//矩阵中所有元素置0 printf("----------------------------\n");
printf("-----指派问题的匈牙利法-----\n");
printf("----------------------------\n");
printf("请输入工作的人数：");
scanf("%d",&PersonCount);
printf("请输入任务数量：");
scanf("%d",&ThingCount);
printf("请输入一个人最多工作的任务数量：");
scanf("%d",&OneDoMaxThing);
printf("请输入0-1指派，按行输入：\n");
for(i=1; i<=PersonCount*OneDoMaxThing; ) // 初始化0-1指派（用户输入）
{
for(j=1; j<=ThingCount; ++j)
{
scanf("%d",&L->assign[i][j]);
}
i += OneDoMaxThing;
for(k=i-OneDoMaxThing+1; k { for(j=1; j<=ThingCount; ++j) { L->assign[k][j] = L->assign[k-1][j]; } } } m = i - OneDoMaxThing; getch(); system("cls"); if(OneDoMaxThing*PersonCount < ThingCount) { m = ThingCount; flag = 0; } else if(OneDoMaxThing*PersonCount > ThingCount) { m = OneDoMaxThing*PersonCount; flag = 1; } printf("该问题可化作如下矩阵：\n"); Print(L->assign,m,m); if(flag == 0) { for(i=1; i<=m; ++i) { reduceRow(L,i,m); } } else { for(j=1; j<=m; ++j) { reduceCol(L,m,j); } } printf("减去每行最小值后，其结果为：\n"); Print(L->assign,m,m); count_Count = 1; do { count = CountZero(L,m,m,1); Zero_marker(L,count,m); ++count_Count; if(count == 0) { removeMarker(L,m); count = CountZero(L,m,m,0); if(count <= m) { SearchAgainByRowReduce(L,count,m); } else { SearchAgainByColReduce(L,m,count); } removeMarker(L,m); count_Count = 1; getch(); puts(""); Print(L->assign,m,m); } }while(count_Count < m); do { for(i=1; i<=m; ++i) { for(j=1; j<=m; ++j) { if(L->assign[i][j] == 0) { count1[i]++; } } } for(j=1; j<=m; ++j) { for(i=1; i<=m; ++i) { if(L->assign[i][j] == 0) { count1[m+j]++; } } } for(k=1; k { count = 1; for(i=1; i<=m*2; ++i) { if(count1[count] < count1[i]) { count = i; } } Zero_marker(L,count,m); count1[count] = 0; for(i=1; i<=m; ++i) { for(j=1; j<=m; ++j) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { flag = 2; } } } for(i=1; i<=m; ++i) { int t = 0; for(j=1; j<=m; ++j) { if(L->assign[i][j] != 0) { t++; } } if(t == m) { flag = 1; break; } } if(flag != 2 ) { removeMarker(L,m); count = CountZero(L,m,m,0); if(count <= m) { SearchAgainByRowReduce(L,count,m); } else { SearchAgainByColReduce(L,m,count); } } }while(flag != 2); puts(""); Print(L->assign,m,m); getch(); printf("其结果为：\n"); Print(L->assign,m,m); getch(); system("cls"); printf("本问题的最优解为：\n"); removeMarker(L,m); count = CountZero(L,m,m,0); ToBest(L,count,m); for(i=1; i<=m; ++i) { for(j=1; j<=m; ++j) { if(L->assign[i][j] != 0) { L->assign[i][j] = 1; } } } Print(L->assign,m,m); getch(); free(L); L = NULL; return 0; } void Print(int a[][MAXCOUNT],int Row,int Col) { int i,j; for(i=1; i<=Row; ++i) { for(j=1; j<=Col; ++j) { printf("%-4d",a[i][j]); } puts(""); } } void reduceRow(Assign*L,int Row,int Col) { int j; int min; min = L->assign[Row][1]; for(j=1; j<=Col; ++j) { if(min>L->assign[Row][j]) { min = L->assign[Row][j]; } } for(j=1; j<=Col; ++j) { L->assign[Row][j] -= min; } } void reduceCol(Assign*L,int Row,int Col) { int i; int min; min = L->assign[1][Col]; for(i=1; i<=Row; ++i) { if(min>L->assign[i][Col]) { min = L->assign[i][Col]; } } for(i=1; i<=Row; ++i) { L->assign[i][Col] -= min; } } int CountZero(Assign*L,int Row,int Col,int temp) { int i,j,max_Zero = 1,flag = 0,count[2*(MAXCOUNT+1)] = {0}; for(i=1; i<=Row; ++i) { for(j=1; j<=Col; ++j) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { count[i]++; flag = 1; } } } for(j=1; j<=Col; ++j) { for(i=1; i<=Row; ++i) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { count[Row+j]++; flag = 1; } } } if(flag == 1) { for(i=2; i<=Row*2; ++i) { if(temp == 1) { if(count[i]>count[max_Zero]) { max_Zero = i; } } else { if(count[i] { max_Zero = i; } } } return max_Zero; return 0; } void Zero_marker(Assign*L,int m,int n) { int i,j; if(m <= n) { for(j=1; j<=n; ++j) { L->sign[m][j].marker = TRUE; } } else { for(i=1; i<=n; ++i) { L->sign[i][m-n].marker = TRUE; } } } void SearchAgainByRowReduce(Assign*L,int count,int m) { int j,t,temp,min = 1; while(L->assign[count][min] == 0) { min++; } for(j=2; j<=m; ++j) { if(L->assign[count][j] < L->assign[count][min] && L->assign[count][j] != 0) { min = j; } } temp = L->assign[count][min]; for(j=1; j<=m; ++j) { L->assign[count][j] -= temp; } for(j=1; j<=m; ++j) { if(L->assign[count][j] < 0) { temp = L->assign[count][j] * -1; for(t=1; t<=m; ++t) { L->assign[t][j] += temp; } } } } void SearchAgainByColReduce(Assign*L,int m,int count) { int i,t,temp,min = 1; while(L->assign[min][count-m] == 0) { min++; } for(i=2; i<=m; ++i) { if(L->assign[i][count-m] < L->assign[min][count-m] && L->assign[min][count-m] != 0) { min = i; } } temp = L->assign[min][count-m]; for(i=1; i<=m; ++i) { L->assign[i][count-m] -= temp; } for(i=1; i<=m; ++i) { if(L->assign[i][count-m] < 0) { temp = L->assign[i][count-m] * -1; for(t=1; t<=m; ++t) { L->assign[i][t] += temp; } } } } void removeMarker(Assign*L,int m) { int i,j; for(i=1; i<=m; ++i) { for(j=1; j<=m; ++j) { L->sign[i][j].marker = FALSE; } } } void ToBest(Assign*L,int count,int m) { int i,j,t,a[MAXCOUNT] = {0}; if(count <= m) { for(j=1; j<=m; ++j) { for(i=1; i<=m; ++i) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { a[j+m]++; } } } for(j=m+1; j<=2*m; ++j) { if(a[j] == 1) { for(i=1; i<=m; ++i) { if(L->assign[i][j-m] == 0 && L->sign[i][j-m].marker == FALSE) { L->assign[i][j-m] = INDEF; for(t=0; t<=m; ++t) { if(L->assign[i][t] != INDEF) { L->assign[i][t] = 0; L->sign[i][t].marker = TRUE; } } L->sign[i][j-m].marker = TRUE; } else { L->assign[i][j-m] = 0; L->sign[i][j-m].marker = TRUE; } } ToBest(L,j,m); break; } } } else { for(i=1; i<=m; ++i) { for(j=1; j<=m; ++j) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { a[i]++; } } } for(i=1; i<=m; ++i) { if(a[i] == 1) { for(j=1; j<=m; ++j) { if(L->assign[i][j] == 0 && L->sign[i][j].marker == FALSE) { L->assign[i][j] = INDEF; for(t=1; t<=m; ++t) { if(L->assign[t][j] != INDEF) { L->assign[t][j] = 0; L->sign[t][j].marker = TRUE; } } L->sign[i][j].marker = TRUE; } else { L->assign[i][j] = 0; L->sign[i][j].marker = TRUE; } } ToBest(L,i,m); break; } } } } 四、算例和结果 本程序以课本上例4-10为例： 例4-10 某商业公司计划开办五家新商店 54321,,,,B B B B B ,为了尽早建成营业，现有五家建筑公司54321,,,,A A A A A ,以便让每家新商店由一个建筑公司承建。建筑公司i A 承建新商店j B 的建造费用投标ij C 为（i,j = 1,2,3,4,5）,其值如下图所示。商业公司应如何分配，使建造总费用最少？ 1 A 1 B 2B 3B 4B 5B i A j B )10/(4 元ij C 4871512 程序运行结果如下（包含程序运行中间步骤）： 该问题最终演化为如下0-1矩阵： 即该问题的解为5544132231,,,,B A B A B A B A B A -----。(注释：‘-’前为建筑公司，后面为该建筑公司所承建的商店。) 即最少费用 为 min = （7 + 9 + 6 + 6 + 6 ） * 410= 34 * 410 元。 五、结论和总结 本程序可以解决一个人一个任务，或者一个人多个任务的消耗费用最优问题。通过此次课程设计,更加清楚的了解到匈牙利算法的思想及其实现，同时也对C 语言更加熟悉。 此程序不足之处： 本程序中使用了较多的函数，但其中有两个函数的功能大体一致，到最后也未能将其整合到一个函数，使得此代码太长；同时此程序中有几处代码看起来太过复杂，也显得太过累赘，还可以进行优化。出现的操作界面太过单调，不够美观。 《东欧社会主义国家的改革与演变》资料 匈牙利事件 在东欧国家中，受苏共“二十大”影响、政局动荡最为剧烈的是匈牙利。1956年春，随着苏联展开对斯大林的批判，匈牙利也兴起了要求民族自主和改革的潮流。3月17日，布达佩斯的一批新闻界、文学艺术界和教育界人士（包括部分党员干部）成立以爱国诗人裴多菲命名的俱乐部。他们组织各种会议，在报刊发表文章，评论时政，批评以拉科西为首的党和政府所推行的照搬苏联模式的路线和政策，要求恢复因提出改革政策而被开除出党的前总理纳吉的职务，在经济和政治领域实行全面改革，并呼吁为被指控为“铁托分子”而遭清洗、迫害乃至处死的前外交部长拉伊克等人平反。裴多菲俱乐部的活动引起社会强烈反响，有些讨论会参加者多达数千人，成为舆论关注的热点。但是，拉科西拒不接受党内外的批评，站在群众的对立面，并用“反党反人民”的罪名镇压裴多菲俱乐部。拉科西的倒行逆施进一步激化了社会矛盾，使社会动荡加剧，也引起苏联当局的不安。7月17日，苏共领导人米高扬到布达佩斯参加匈党中央会议，决定让拉科西下台，由格罗接任党中央第一书记，增补卡达尔为中央书记。然而，领导人的更换未能使局势稳定下来，因为格罗继续奉行拉科西的路线，党内外的不满情绪不仅没有平息，反而进一步增长。 10月6日，在群众的压力下，党中央决定为被冤杀的拉伊克等4人举行国葬，布达佩斯三十多万居民自发上街为拉伊克送葬，此举成为群众对当局的一次大示威。为了缓和形势，格罗被迫于10月14日宣布恢复纳吉的党籍，但这一让步已不能解决问题。10月21日，哥穆尔卡出任波兰党中央第一书记的消息传到布达佩斯，引起连锁反应。次日，裴多菲俱乐部和布达佩斯大专院校学生团体联席会议先后向党中央、政府提出十点要求和十六点要求，主要内容是：清算拉科西的罪行，将其开除出党；改组党的领导机关，由纳吉出来主持政府工作；进行经济和政治体制改革；撤走苏联驻军，维护民族独立和尊严等。格罗对此反应迟钝，没有采取任何措施。在这种情况下，群众的不满和愤怒终于以激烈的方式爆发了。 10月23日，布达佩斯的大学生首先走上街头，举行示威游行，当局先是下令禁止，后见阻挡不住又解除禁令。游行队伍迅速壮大，各界人士纷纷加入，傍晚，聚集在市中心广场的群众已达二十余万。晚8时，格罗发表广播讲话，对游行示威进行谴责，声称要镇压“暴徒”。这犹如火上浇油，事态急剧恶化，一部分示威者冲击电台，与保安部队发生冲突。当晚，电台、电信局、党中央机关报、印刷厂和一些警察局被示威者占领。 鉴于形势严重，当日深夜召开的党中央紧急会议决定由纳吉出任政府总理，同时决定全国戒严并请求苏联出兵维持秩序。这些决定于次日上午公布，随即，驻匈苏军的坦克进入布达佩斯。25 第 26 章链表、二叉树和哈希表 3. 哈希表 下图示意了哈希表（Hash Table）这种数据结构。 图 26.12. 哈希表 如上图所示，首先分配一个指针数组，数组的每个元素是一个链表的头指针，每个链表称为一个槽（Slot）。哪个数据应该放入哪个槽中由哈希函数决定，在这个例子中我们简单地选取哈希函数h(x) = x % 11，这样任意数据x都可以映射成0~10之间的一个数，就是槽的编号，将数据放入某个槽的操作就是链表的插入操作。 如果每个槽里至多只有一个数据，可以想像这种情况下search、insert和delete 操作的时间复杂度都是O(1)，但有时会有多个数据被哈希函数映射到同一个槽中，这称为碰撞（Collision），设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中，尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中，每个糟里约有n/m个数据，则search、insert和delete和操作的时间复杂度都是O(n/m)，如果n和m的比是常数，则时间复杂度仍然是O(1)。一般来说，要处理的数据越多，构造哈希表时分配的槽也应该越多，所以n和m成正比这个假设是成立的。 请读者自己编写程序构造这样一个哈希表，并实现search、insert和delete 操作。 如果用我们学过的各种数据结构来表示n个数据的集合，下表是search、insert 和delete操作在平均情况下的时间复杂度比较。 表 26.1. 各种数据结构的search、insert和delete操作在平均情况下的时间复杂度比较 数据结构search insert delete O(n)，有序数组折半查找是O(lgn)O(n)O(n) 数组 双向链表O(n)O(1)O(1) 排序二叉树O(lgn)O(lgn)O(lgn) 哈希表（n与槽数m成正比）O(1)O(1)O(1) 习题 1、统计一个文本文件中每个单词的出现次数，然后按出现次数排序并打印输出。单词由连续的英文字母组成，不区分大小写。 2、实现一个函数求两个数组的交集：size_t intersect(const int a[], size_t nmema, const int b[], size_t nmemb, int c[], size_t nmemc);。数组元素是32位int型的。数组a有nmema个元素且各不相同，数组b有nmemb个元素且各不相同。要求找出数组a和数组b的交集保存到数组c中，nmemc是数组c 的最大长度，返回值表示交集中实际有多少个元素，如果交集中实际的元素数量超过了nmemc则返回nmemc个元素。数组a和数组b的元素数量可能会很大（比如上百万个），需要设计尽可能快的算法。 细数中国与匈牙利的那些渊源 中匈关系 1949年，中匈两国正式建交，是最早承认新中国的国家之一。 1992年5月，布达佩斯—中国贸易中心开业。 2004年5月，匈牙利加入欧盟。 2007年，匈牙利加入申根国。 2009年，罗兰大学建立孔子学院。 2011年，国务院总理温家宝访问匈牙利，中国购买匈牙利国债，并为匈牙利提供10亿欧元的贷款基金。 2013年4月，匈牙利国债移民项目启动。 匈牙利经济状况 ?GDP总量：1940亿美元，（世界排名第50位） ?人均GDP；1.9亿美元，（世界排名第48位，中国人均6200美元，排名第89位） ?其中私营企业占GDP比重的80% ?产业结构：工业33%、农业3%、服务业64% ?主要产业：旅游、葡萄酒、机械、汽车、制药。 教育概况 ?匈牙利人口998万，出过14位诺贝尔奖获得者，是世界上人均得诺贝尔奖最高的国家之一。 ?匈牙利教育投入占GDP总量的5.2，世界排名第18位（中国2.79% , 世界排名第140位） ?12年义务教育（无书本费、学杂费等，实行真正的义务教育制度） ?匈牙利拥有中匈双语的公立教育，以及英美的私立国际教育学历, 全世界认可。 医疗 ?匈牙利拥有世界领先的医疗体系和基础设施（以牙科和心脏科闻名）?匈牙利医疗支出占GDP的7.3%，世界排名第66位（中国1.21%，世界排名第145位） ?匈牙利国家医疗保险费用为每人25欧元每月 ?除营养品和保健品外，其余全在医疗保险范围内（急诊无论有无医疗保险，都实行优先救治原则） ?医保卡适用于全欧盟国家。 社会保障 ?匈牙利实行“国家保障型”的社会保障制度，包括全国统一的退休金保障、全面公费医疗、家庭津贴、教育补贴、消费补贴、住房补贴以及其他公共福利事业等。 ?社会保障总投入占GDP的36.9%（中国12%） ?匈牙利失业率5.4%，低于欧盟平均水平（欧盟10.9%） ?布达佩斯物价除电子产品外，均略低于天津。 自然环境 ?匈牙利森林覆盖率22.5%（中国2%） ?拥有欧洲最多的温泉疗养胜地Hevis,Miskoic等 ?拥有欧洲最大的淡水湖巴拉顿湖，是全世界知名的度假风景区. 姓名： 报考专业： 准考证号码： 密封线内不要写题 年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C 语言版） 科目代码：考试时间：3小时 满分 150 分 可使用的常用工具：√无 □计算器 □直尺 □圆规（请在使用工具前打√）所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 小题，每小题2分，共20分) （最多元素为MaxSize ）为空时，其栈顶指针top 栈满的条件是（ ）。 ST.top != -1 B ）ST.top == -1 ST.top != MaxSize – 1 D ）ST.top == MaxSize –是结点 p 的直接前趋，若在 q 与 p 之间插入结点 9. 在Hash函数H(k)=k MOD m中，一般来讲m应取（）。 A）奇数 B）偶数 C）素数 D）充分大的数 10.用二分插入排序法进行排序，被排序的表应采用的数据结构是（）。 A）数组 B）单链表 C）双向链表 D）散列表 二、填空题(共10小题，每小题2分，共20分) 1. 一个栈的入栈序列为1,2,3,…,n，其出栈序列是p1,p2,p3,…,pn。若p2 = 3， 则p3可能取值的个数是（）。 2. 已知单链表A长度为m，单链表B长度为n，若将B连接在A的末尾，在没有链 尾指针的情形下，算法的时间复杂度应为（）。 3. 从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的 情况下，需要平均比较（）个结点。 4. 对于一个有N个结点、K条边的森林，共有（）棵树。 5. 若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是 （）。 6. 有向图包含5个顶点（编号从1到5）6条弧（<1,2>,<1,5>,<1,3>,<2,3>, <3,4><5,4>）。该图进行拓扑排序，可以得到（）个拓扑序列。 7. 对于一个有向图，若一个顶点的入度为k1,出度为k2，则对应邻接表中该顶点 邻接点单链表中的结点数为（）。 8. 设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32， 13，49，24，38，21，4，12）按线性探测法解决冲突的方法构造哈希表，则该哈希表等概率下查找成功的平均查找长度为（）。 9. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）。 10. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元 素进行比较，将其放入已排序序列的正确位置上的方法称为（）。 三、判断题(对的答√错的答×，共10小题，每小题2分，共20分) 1. 不论是入队列还是入栈，在顺序存储结构上都需要考虑“溢出”情况。 2. 在顺序表中取出第i个元素所花费的时间与i成正比。 3. 线性表的插入、删除总是伴随着大量数据的移动。 4. 二叉树通常有顺序存储结构和链式存储结构。 5. 对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一 定不小于下一层任一结点的权值。 6. Prim 算法通过每步添加一条边及相连顶点到一棵树，从而生成最小生成树。 7. 用邻接矩阵存储图，占用的存储空间只与图中结点数有关，而与边数无关。 8. 散列查找主要解决的问题是找一个好的散列函数和有效解决冲突的办法。 9. 对长度为10的排好序的表用二分法检索，若检索不成功，至少需比较10次。 10. 对5个不同的数排序至少需要比较4次。 四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分) 1. 分别给出在先序线索二叉树、中序线索二叉树和后序线索二叉树中结点p的直 接后继结点所在位置。 线索二叉树中结点的结构包括数据域data、左孩子域left、右孩子域right、 指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。 ???????? ??????????? ? ?0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。 2、 确定独立零元素，并作标记。 （1）、首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。 （2）在按行处理时，若某行有独立0元素，把该0元素标记为a ，把该0所在的列中的其余0元素标记为b ；否则，暂时越过本行，处理后面的行。把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a 标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。 （3）在按列处理时，若某列有独立0元素，把该0元素标记为a ，把该0所在的行中的其余0元素标记为b ；否则，暂时越过本列，处理后面的列。把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a 标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。 （4）、重复上述过程，即得到独立零元素（标记a 的“0”） ???????? ??a b b a b b a 0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤： （1）、对没有标记a 的行作标记c （2）、在已作标记c 的行中，对标记b 所在列作标记c （3）、在已作标记c 的列中，对标记a 所在的行作标记c （4）、对没有标记c 的行划线，对有标记c 的列划线 ??????? ? ??04320405001232037710 811030 / / / / / \/ \/ 一、该程序实现的哈希表：构造哈希函数的方法为除留余数法(函数modhash)，处理哈希冲突的方法为链地址法。 二、对哈希表的操作：插入（函数hash_table_insert）、移除（函数hash_table_remove）、 查找（函数hash_table_lookup）、整个哈希表的释放（函数hash_table_delete）、 整个哈希表的输出（函数hash_table_print）。 三、哈希表的最大长度可以由HASHMAXLEN设置（我设为1000）。 四、输入哈希表的名称拼音字符是长度为10—20（长度可由STR_MAX_LEN和STR_MIN_LEN）的小写字母组成。这些名字字符串是我用函数rand_str随机产生的。 五、名称拼音字符（关键字）到关键字值的转换方法：先把名称的拼音字符转换对应的ASCII，累加后作为关键字值。我是用函数str_to_key实现的。 六、异常情况包括： 1、在对哈希表进行插入操作时，若哈希表的实际长度超过了哈希表的最大长度，我就输出“out of hash table memory!”，然后直接跳出插入子函数，不进行插入操作。 2、在对哈希表进行插入操作时，若插入的元素在哈希表中已经存在，我就输出“******already exists !”，然后直接跳出插入子函数，不进行插入操作。 3、在对哈希表进行查找操作时，若查到则返回其地址，若没查到则返回空地址。 4、在对哈希表进行移除操作时，对同义词元素的删除，分为表头和表中两种情况处理。 七、开发平台：DEV-C++，用c语言实现。 在哈希表程序中我比较注重整个代码风格，希望能形成很好的代码风格！如果有什么可以改进的，希望老师能跟我说说！ 运筹学 课 程 设 计 报 告 专业： 班级： 学号： ： 2012年6月20日 目录 一、题目。 二、算法思想。 三、算法步骤。 四、算法源程序。 五、算例和结果。 六、结论与总结。 一、题目：匈牙利法求解指派问题。 二、算法思想。 匈牙利解法的指派问题最优解的以下性质： 设指派问题的系数矩阵为C=()c ij n n?，若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C’=()'c ij n n?。那么，以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。 由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常 数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无 负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否 得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。 三、算法步骤。 （1）变换系数矩阵，使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。 （2）做能覆盖所有零元素的最少数目的直线集合。 因此，若直线数等于n，则以可得出最优解。否则，转第（3）步。 对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第（1）步的基础上，若能找到n个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（1）步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。 此时，可以从零元素的最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行合同列的其他零元素划去（标记为），如此逐步进行，最终可得n个位于不同行、不同列的零元素，他们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。需要对零元素的分布做适当调整，这就是第（3）步。 （3）变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（2）步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。 四、算法源程序。 匈牙利法 假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表2－6所示。 请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？ 表2－6 各员工完成任务时间汇总表单位：小时 注意：由于存在以下两种情况，匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，但最终配置结果一定相同， 1．约减时，可先进行行约减，再进行列约减；也可先进行列约减，再进行行约减。2．“盖0”线的画法不唯一。 现列举两种解法如下： 解法一： 1．以各个员工完成各项任务的时间构造矩阵一。 表2－7矩阵一 10 5 9 18 11 13 19 6 12 14 3 2 4 4 5 18 9 12 17 15 11 6 14 19 10 2．对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。 表2－8 矩阵二 5 0 4 13 6 7 13 0 6 8 1 0 2 2 3 9 0 3 8 6 5 0 8 13 4 3．检查矩阵二，若矩阵二各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。 表2－9 矩阵三 4 0 4 11 3 6 13 0 4 5 0 0 2 0 0 8 0 3 6 3 4 0 8 11 1 4．画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得图2－5。 图2－5 矩阵四 操作技巧：从含“0”最多的行或列开始画“盖0”线。 5．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下： （1）找出未被“盖0”线覆盖的数中的最小值λ，例中λ＝1。 （2）将未被“盖0”线覆盖住的数减去λ。 （3）将“盖0”线交叉点的数加上λ。 本例结果见表2－10 矩阵五。 表2－10 矩阵五 3 0 4 10 2 5 13 0 3 4 0 1 3 0 0 7 0 3 5 2 3 0 8 10 0 6．重复4步和5步（计算过程见矩阵五a和矩阵五b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表2－11。 矩阵五a [摘要]在工业化和城市化发展过程中，欧洲各国先后建立了社会保障制度。此后，欧洲各国又相继跨入了人口老龄化国家行列。为了应对人口老龄化的冲击，各国对本国的养老体制不断改革，以保持人口、社会和经济之间的协调发展。 在工业化和城市化发展过程中，欧洲各国先后建立了社会保障制度。此后，欧洲各国又相继跨入了人口老龄化国家行列。为了应对人口老龄化的冲击，各国对本国的养老体制不断改革，以保持人口、社会和经济之间的协调发展。 为了借鉴欧洲的经验，2006年10月9日至19日，中国社会科学院代表团以人口老龄化与养老体制改革为主题，对荷兰、挪威和匈牙利三国进行了深入考察。本报告根据考察情况和相关资料，对荷兰、挪威和匈牙利三国迎接老龄化社会挑战等方面的具体做法加以介绍，旨在通过借鉴其经验，为推进我国养老保险事业的健康发展提供有益参考。 一、荷兰的养老保险体系及其政策改革 荷兰人口数量为1630万人，人口规模在西欧国家中处于中等偏上，人均收入水平却位居西欧国家前列。2005年，荷兰人口老龄化水平为14.1%，低于意大利、德国、法国。据预测，荷兰人口老龄化到2015年将超过欧洲的平均水平，到2050年老年抚养比将上升到43.0%，几乎两个劳动力抚养一个老人。 （一）荷兰的养老保险制度 荷兰养老保险体系由国家养老金、职业养老金和个人养老金三个支柱组成。其中，国家养老金是基础，职业养老金占主导地位，个人养老金是补充。1957年，荷兰出台了《一般养老金法》。该法规定，所有在荷兰居住50年以上的65岁以上的人都能获得统一的国家养老金。国家养老金是一个现收现付的、受益金额固定的养老保险计划，国家通过税收来源为每个公民提供最低收入支持。国家养老金提供的保障水平低，相当于最低工资水平的70%。它的给付按照参加保险时间长短计算，每年按照2%的比例递增。如果从15岁到64岁都参加了这项保险，在65岁退休时可获得百分之百的国家养老金。 职业养老金制度是从上世纪60年代开始建立的，国家制定规则，由雇主与雇员签订相关协议。荷兰的工会和雇主组织都很发达，它们对职业养老金制度的形成和改革有着重要影响。一般而言，职业养老金计划缴费采取按照最终工资或平均工资来计算，收益按照加入时间长短来计算，每年按照工资替代率2%左右的比例增加，这样，如果集体双方达成35年的协议，工人在退休时的养老金收益收入相当于其最后工资的70%（包括国家养老金在内）。职业养老金的缴费由雇员和雇主匹配缴费，雇员缴纳占1/3或1/2。2003年，荷兰大约有91%的劳动者加入了各种职业养老基金。 个人养老金计划完全根据个人自愿决定是否加入商业保险计划。这类计划有年金保险和人寿保险等方式，它所反映的是个人与商业保险公司之间关系，而不是雇主和员工之间的关系。荷兰政府通过制定非常详细、精确的财税政策，利用税收杠杆鼓励个人加入这项计划。 （二）荷兰的养老体制改革与养老金运行管理 为了减缓人口老龄化对养老体制的冲击，荷兰从上个世纪90年代以来进行了一系列改革。1997年，荷兰对国家养老金占个人养老金收益比例设置最高幅度，限制其进一步增长。同时，荷兰也加快了对第二支柱的改革。例如，取消80年代出台的早退休计划，将其改为灵活的职业养老金计划，让雇员在退休年龄与退休收益之间进行选择。将职业养老金缴费计算从最终工资改为平均工资，养老金调整改为有条件的指数化，以及加强资金的财务约束和采取透明化管理等等。 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。 运输问题的解法 运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许 多其它问题也归结到这一类问题中。正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。 §1 运输问题的数学模型及其特性 1.1 运输问题的数学模型 设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销 地或收地） ，各个发点需要调出的物资量分别为 个单位，各个收点需要调进的物资量分别为 个单位。已知每个发点 到每个收点 的物 资每单位运价为 ，现问如何调运，才能使总的运费最小。我们把它列在一张表上（称为 运价表）。设 表示从产地 运往 销地的运价（ =1，2，…， ； =1，2，…， ）。 表3-1 如果（总发量） （总收量），我们有如下线性规划问题： m m A A A ,,,21 n n B B B ,,,2 1 m a a a ,,,21 n b b b ,,,21 i A j B ij c ij x i A j B i m j n ∑∑===m i n j ij ij x c z 11 min （3.1） （3.1）式称为产销平衡运输问题的数学模型。当（总发量） （总收量） 时。即当产大于销（ ）时，其数学模型为 （3.2） 当销大于产（ ）时，其数学模型为 （3.3） 因为产销不平衡的运输问题可以转化为产销平衡的运输问题。所以我们先讨论产销平衡的运输问题的求解。 运输问题有个未知量,个约束方程。例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。我们必须寻找特殊解法。 1.2 运输问题的特性 由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一 ????? ??????==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1 1n j m i x n j b x m I a x ij j m i ij i n j ij ∑∑==≠n j j m i i b a 1 1 ∑∑==>n j j m i i b a 1 1 ∑∑===m i n j ij ij x c z 11 min ????? ??????==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1 1n j m i x n j b x m I a x ij j m i ij i n j ij ∑∑== 民政厅赴俄罗斯匈牙利社会保障社会救助考察报告 民政厅副厅长为组长的考察组一行3人赴俄罗斯和匈牙利两个国家进行为期10天的考察，就社会保障、社会救助等方面与俄罗斯、匈牙利有关政府部门、社会组织进行友好交流，并参观了部分养老、救助服务机构和国家公墓等福利设施。现将有关考察情况汇报如下： 一、考察俄罗斯情况 在俄罗斯期间,考察组先后到了莫斯科和圣彼得堡两个城市。莫斯科是俄罗斯首都、第一大城市和政治、经济、科学、文化和交通的中心。考察组到莫斯科的第二天上午，就专程拜访了莫斯科市社会保障厅。莫斯科市社会保障厅是负责全市社会保障和社会事务工作的职能部门，该厅第一（首席）副厅长格拉乔娃?奥列格?叶夫盖尼耶夫娜女士特意安排时间会见了考察组一行，并召集了厅保障基金管理部、人道主义帮助部、计划和人文保障部、社会服务与应用管理部等4 个部门的负责人，与考察组进行了三个小时亲切友好的会谈。格拉乔娃?奥列格?叶夫盖尼耶夫娜副厅长首先向考察组详细介绍了莫斯科市社会保障的有关情况：莫斯科市现有人口1300万，其中常驻人口1000万，流动人口300万。社会保障厅有工作人员200余人，全市有专职社会工作者30多万人，各类社会服务机构322所，需要保障的家庭有300万多个。社会保障厅主要负责三个方面的工作： 1、老年人生活保障。莫斯科市现有退休人员200多万人，其退休金由三部分组成，即国家承担基础金（或称低保金）1200卢布/月、养老保险金、个人积累。大部分老年人实行居家养老，由社会工作者为需要照料的老年人提供必要的服务（如购物、做饭、送医就诊等），每个社会工作者负责8名需要照料的老年人。莫斯科市设有老年福利机构122所、养老院37所（均为公办），老年福利机构主要是帮助老年人的日常活动和日间照料；养老院主要收养参加过卫国战争的老战士，所需经费全部由俄罗斯政府承担。随着经济社会的发展，老年人养老需求的日益增加，莫斯科市社会保障厅也开始探索发展非国有制养老院和开展社会 现在世界上有哪些国家是社会主义国家,有哪些是君主立宪制国家 现在是社会主义制度的国家 中华人民共和国 朝鲜民主主义人民共和国 古巴共和国 越南社会主义共和国 老挝人民民主共和国 曾实行社会主义制度的国家 捷克斯洛伐克（至1989年） 匈牙利（至1989年） 罗马尼亚（至1989年） 保加利亚（至1989年） 波兰（至1989年） 民主德国（至1990年） 阿尔巴尼亚（至1991年） 苏联（至1991年） 蒙古人民共和国(至1991年) 南斯拉夫社会主义联邦共和国(至1991年) 国名带社会主义但并未实行社会主义制度的国家 大阿拉伯利比亚人民社会主义民众国 斯里兰卡民主社会主义共和国 详细情况请直接点以下网址： https://www.sodocs.net/doc/2a13748482.html,/zh/%E7%A4%BE%E6%9C%83%E4%B8%BB%E7% BE%A9%E5%9C%8B%E5%AE%B6.htm#.E7.8E.B0.E5.9C.A8.E6.98.AF.E7. A4.BE.E4.BC.9A.E4.B8.BB.E4.B9.89.E5.88.B6.E5.BA.A6.E7.9A.84.E5.9B.BD .E5.AE.B6 目前世界上的君主立宪制国家一般认为有： 欧洲：英国、挪威、瑞典、丹麦、荷兰、比利时、卢森堡、西班牙、安道尔、摩纳哥、列支敦士登 君主立宪制，或称「虚君共和」，是一种国家的体制。君主立宪是在保留君主制的前提下，通过立宪，树立人民主权，限制君主权力，实现事实上的共和政体。其特点是国家元首是一位君主（皇帝、国王、大公等等，教宗有时也被看做是一个君主）。与其他国家元首不同的是，一般君主是终身制的，君主的地位从定义上就已经高於国家的其他公民（这是君主与一些其他元首如独裁者的一个区别，一般独裁者将自己定义为公民的一员，但出於客观需要他必须掌权为国家服务）， ：利用哈希技术统计C源程序关键字出现频度 目录一．需求分析说明 (3) 二．总体设计 (3) 三．详细设计 (4) 四．实现部分 (5) 五．程序测试 (10) 六．总结 (11) 一、需求分析说明 1.课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 2.题目要求 1)题目内容： 利用Hash技术统计某个C源程序中的关键字出现的频度 2)基本要求： 扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为： Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41 二、总体设计 一．算法思想描述 首先读取关键字文件以建立二叉排序树以供后续查询，每个树节点保存一个关键字字符串及指向左右子树的指针。同时创建一Hash表，每个节点除应保存关键字字符串外，还应保存关键字频数及该存储单元冲突次数。然后扫描一个C源程序，每次扫描一行，从中循环分离出每个单词，每次均查找其是否为关键字，若是，则按计算公式计算其KEY值并在Hash表中进行相应操作，若该节点为空则插入否者比较其是否与现有关键字相同，若相 同则增加其频数，否则增加其冲突次数并继续线性探测下一个存储单元，完了继续操作下一个分离出来的单词，如此循环运行直至扫描结束。编写本程序时，使用了二叉树创建、二叉树查找、Hash表的建立和操作及文件操作等基本算法。 二．三、详细设计 (程序结构 //Hash表存储结构 typedef struct node //定义 { char s[20]; int num,time; //num为频数，time为冲突次数 }node; //二叉排序树结构定义 typedef struct nod //定义 { char s[20]; struct nod *left,*right; }nod; int max;//max为Hash表长度 指派问题的解法总结 问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制， 每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称 为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对 于不是一对一的，则可以通过文献1中的一些方法进行变换。 目前问题解法的总结。 1：最广泛应用的解法：匈牙利算法。 算法简介：库恩（fW．W．Kuhn)于1955年提出了指派问题的解法．他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等 于覆盖所有0元素的最少直线数。这个解法称为匈牙利解法。 匈牙利算法虽是运用最广泛的算法，但其操作过程却过于复杂。在划0的时候也不方 便记忆，对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单，方便易记的算法。 2：指派问题新解法——目标值子矩阵法。 算法描述：任取变量矩阵X某一行中的最小元素，为该行元素目标值的最优解(但 不一定是系统目标函数的最优解)，应该是系统目标函数满意解中的一个元素，记作 a11 划去a11 所在的行和列，取剩下的子矩阵中某一行的最小元素，记作a22。依次 类推，直到最后一个元素a nn．这些元素相加得系统目标函数的一个满意解，此为一 次运算．第二次运算取变量矩阵X中含a 以外的任一行，做与上面相同运算，又可以 得到系统的第二个满意解．相同地，对于n行做n次运算，共得到系统的n个满意解，系统的最优解即应该是这 n个满意解当中的最小值．若第i的最小元素在前面以被取 用过，则在进行第i的运算时，不选取该元素，取该行中未被选用过的元素中最小的一个进行运算。 算法分析：相对于匈牙利算法，此算法简单，方便操作。但不能给出所有最优解，得出的最优解唯一，若要给出全部最优解，则算法的次数将大大增加。 当矩阵维数较大的时候，可以对矩阵进行划分，以更快计算。 算法举例：对于变量矩阵x； ?其实匈牙利在二战中也算个角色 ? ?文章提交者：panzerxj 加贴在历史风云图区铁血论坛https://www.sodocs.net/doc/2a13748482.html,/bbs66-0-1.html ? ? 奥匈帝国时期皇家匈牙利军队和匈牙利普通军队都穿深蓝色制服，从1908年开始蓝灰色系列（1915年时则是绿灰色系列）的野战服和常服开始使用，并搭配以带匈牙利式绳结的义务兵用细腿裤子以及军官用圆筒平顶军帽、野战用大盖帽和德国的M1917式钢盔。 [ 转自铁血社区https://www.sodocs.net/doc/2a13748482.html,/ ] 按A26号制服规则，1920年开始采用改进版本的制服，该制度一直被使用到1945年9月。昂贵的军官用轻骑兵版阿提拉式阅兵服在1931年得到简化。常服和野战服采用了土黄色，并搭配带有topan装饰（一种倒三角形布面上装饰三条编织绳索，绳索尾端带圆形花饰的装饰）的Bocskai式野战帽；制服上衣采用M1919式领章；宽松的步兵裤子在小腿部收紧。军官礼服还搭配黑色（职业士官是棕色）圆筒平顶军帽和长筒裤子。军衔系统、军官的穗带、兵种色（除了步兵和机动部队）、半正式的部队帽徽和三角形的奖章绶带则一直显现着1918年以前的传统。 德国人的影响在战时得到显现，雪地迷彩服、短衣襟的双排扣坦克兵夹克、宽松的步兵裤子、皮质黑色行军靴以及伞兵迷彩工作服都是如此，但是，匈牙利的元素仍是主流。 同样根据A-26号制服规章，1921年河流卫队开始采用深蓝色的军官礼服、上衣带开领和军衔袖章的陆军土黄色常服。军 官戴大盖帽，帽顶配代表军衔的金色环带以及被称为埃里奥特之眼（Elliott Eye）的螺旋形装饰物。准尉在袖子上配戴蓝色陆军版领章，1940年后又加上了代表军衔的银色编织条。低级士官和士兵则戴无帽檐的海军帽，上衣带巨大的白色领子和蓝色的袖标，1940年后又开始采用蓝色横条杠表示军衔。 空军军官最初采用一种类似于河流部队款式的浅土黄色常服，并配戴金色或银色的军衔标和肩章上的黑色背景（将官是深红色）V字形军衔章。带有陆军军衔铭条的雅致的空军制服在1938年8月开始采用，军官戴大盖帽，穿开领上衣，士官和士兵戴无檐海军帽和紧领上衣。 哈希查找算法的源代码 c语言 【问题描述】 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 [基本要求] 假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。 [测试数据] 读取熟悉的30个人的姓名。 #include 九年级历史导学案 年级九班级学科历史课题11、东欧社会主 义国家的改革 与演变 课型新授课 编制人审核人使用时间第 15 周使用人 【学习目标】 1、知道二战后出现的社会主义国家。 2、了解东欧国家改革及其结果。 3、理解东欧剧变的实质。 【重点难点】 重点：匈牙利改革； 难点：东欧剧变的实质。 教学流程 导入： 第一个环节：自主学习、整体感知——（我预习，我自信）：请同学们认认真真阅读课文，初步了解学习内容、学习目标和学习重难点，知道我们今天要学哪些知识点。（有效时间10分钟） 1、心中有数：这节课我要学习几个知识点：每个知识点我准备从哪些方面学习？独立整理本节课的知识点，并在小组进行自学成果展示。 2、眼中有识：通过填空题的形式初步掌握课文 1、阅读第一个标题：“匈牙利的改革”，完成下列问题： （1）背景：二战后，社会主义由____扩大为______国家，东欧社会主义国家大都按照___________________进行经济建设，走了不少弯路。他们先后进行了改革，以推动______的发展，其中改革最突出的是____________。 （2）匈牙利改革内容：（政治、经济两方面，在课本勾画） 作用：____________________________________________________________________。 （3）东欧社会主义国家的改革： 其他东欧社会主义国家进行了不同形式的改革，由于未能摆脱苏联模式以及苏联对东欧国家内政的干涉，改革成效不大。1968年，_______________的改革被苏联镇压。 第三个环节：精讲点拨——（我听讲，我记忆）老师针对本节课的重点、难点、以及在展示中暴露出的问题精讲，请同学们认认真真听讲，做好笔记。（有效时间10分钟） 一、认识： 改革势在必行；社会主义改革发展的道路不会是一帆风顺的；必须坚持实事求是、坚定不移地走社会主义道路。 二、教训： 要进行全面的改革；要深思熟虑、反复实践、科学论证、稳步前进；要高度重视改善人民生活水平；要充分发扬社会主义民主；改革一定要实事求是、符合本国国情、符合经济发展的客观规律。 三、启示： 1、坚持走建设中国特色社会主义道路，坚持独立自主的内外政策； 2、大力发展生产力，提高人民的生活水平，显示社会主义的优越性； 3、建立和健全社会主义民主和法制，实行依法治国； 4、加强执政党的建设，维护党的领导地位。 第四个环节：当堂检测、达标训练——（我实践，我掌握）以选择题和材料题的形式对本节课所学内容进行一个巩固，请同学们先独立完成，然后组内讨论对答案，最后在老师的引导下班内交流。（有效时间是7分钟） 一、能力挑战： 1、社会主义由一国扩大到多国是在（） A．一战后 B．俄国十月革命后 C．二战后 D．美苏争霸后 2、东欧社会主义国家建立以后（） A．学习西欧的发展经验 B．大都按照苏联模式建设 C．大都学习中国的经验 D．走独立发展的道路 3、在东欧剧变前，东欧社会主义国家的改革中较为突出的是（） A．匈牙利 B．罗马尼亚 C．保加利亚 D．捷克斯洛伐克 4、下列有关匈牙利改革的描述，不正确的是（） A．改革前照搬苏联模式，受制于苏联 B．改革摆脱了苏联模式的影响 C．改革健全了民主与法制，稳定了政治局势 D．改革调整了国民经济农、轻、重的比例，促进了经济的发展《东欧社会主义国家的改革与演变》资料：匈牙利事件
ii.c语言本质26链表、二叉树和哈希表3哈希表
细数中国与匈牙利的那些渊源
856数据结构(C语言版)试卷
指派问题的匈牙利解法
该程序实现的哈希表构造哈希函数的方法为除留余数法(
运筹学指派问题的匈牙利法实验报告
人力资源级匈牙利法解题思路
欧洲应对老龄化社会的挑战--荷兰、挪威和匈牙利人口老龄化与养老体制改革考察分析
哈希表的设计与实现-数据结构与算法课程设计报告
运输问题的匈牙利解法和表上作业法
民政厅赴俄罗斯匈牙利社会保障社会救助考察报告
现在世界上有哪些国家是社会主义国家
利用哈希技术统计C源程序关键字出现频度
指派问题的解法
匈牙利军队在二战中的军服
哈希查找算法的源代码 c语言
11东欧社会主义国家的改革与演变