- 浏览: 1397515 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
本篇博文,D.S.Qiu将对《C语言名题精选百则——排列,组合和集合》进行整理推出,不光只是书上的名题,还会依据互联网的资源进行不断补充,加强。等全书各个章节都整理完,会做一个总汇。如果你有建议、批评或补充,请你不吝提出(email:gd.s.qiu@gmail.com,或者直接在本文末评论)。你的支持和鼓励(一个人整理真的很累,几度想放弃),我将渐行渐远!
《排列,组合和集合》主要是介绍了关于有序数组的几个问题,相对简单比较好能理解(点击查看更多数组和字符串问题),主要是对效率的改进,但是要是尽善进美还有待不断的挖掘。下一篇是《排序》(其实就是数论的一些问题),更多关注:http://dsqiu.iteye.com。
问题4.1寻找脚码(ISEARCH.C )
已知一个整数数组x[],其中的元素彼此都不相同,而且也已经从小到大排列好。请用 比较大小、相等的方式编写一个程序,找出给定的数组中是否有一个元素满足x[i]=i的关系。举例而言,如果x[]={-2,-1,3,7,8}, x[3]=3,因此3就是答案。
【说明】
用笨方法,一个循环就可以找出答案,如程序4-1所示。
【程序】
程序4-1
for (index = -1, i=0; i<n, i++)
if (x[i] == i) {
index = i; break;
}
if (index >= 0)
printf("\nFound at x[%d]", index);
else
printf ("\nNot Found")
这个程序在最坏的情况下,for —共绕了 n圈,作了 n次比较,但却没有用到x[]的元素已经排列好的条件。事实上,如果输入有n个元素,应该可以写出与log2n次成正比的比较的程序,关键是X[]的元素是排好顺序的。
【解答】
如果要在一个己经排列好的数组中查找元素,那多半会用到二分查找法,不过这个题 目有点不一样,因为“不知道”要找的数据的值,因此要有点变化才行。首先,要注意两 种情况:
(1)如果x[i]>i,那么对于比i大的任何一个脚码k而言,都会得到x[k]>k,因此 一旦发现了某个i满足x[i]>i时,满足x[j]=j的j就一定只会发生在j<i的所在。
(2)如果x[i]<i,那么对于比i小的任何一个脚码k而言,都会得到x[k]<k,于是 一旦发现了某个i满足x[i]<i时,满足x[j]=j的j就一定只会发生在j>l的所在。
基于上述两种情况,程序就可以找出中间的元素,令它的脚码为middle,比较x[middle] 与middle是否相等,相等的话就找到解答方法了。如果不相等,就看x[middle]>middle 是否成立,如果成立, 那么满足x[i]=i就一定在middle的左边;反之,则在右边。所以这 是一个标准的二分查找法(Binary Search)的变形。
程序要作多少次比较呢?在while中每一个循环都比较两次,一次比相等,一次比大 于。在最坏的情况下,while —共会绕log2n圈,因为每一次要查找的部分都减半,所以总
共会用21og2n次比较。这一项分析与二分查找法完全相同,肯定会比在问题说明中的方法快。
【问题实现】
int index_search(int x[], int n) { int first = 0; int last = n-1; int middle, index; index = -1; while (first <= last) { /* a modified binary search*/ middle = (first + last) / 2; if (x[middle] == middle) { index = middle; break; } else if (x[middle] > middle) last = middle - 1; else first = middle + 1; } return index; }
【习题】
(1)请证明上述的两种情况。
(2)这个程序是基于数组中元素完全相异的前提下做出来的,请问当有重复的元素, 但仍然从小到大排好时,这个程序还能够正常运行吗?为什么?如果不能正常运行,请改 写这个程序。
问题4.2寻找固定的和(FIXSUM.C)
有两个数组x[]与y[],各有m与n个元素,而且各个元素并没有依顺序排烈;且d是 一个已知的值。编写一个程序,看看在对x[]与y[]中有没有满足x[i]+y[j]=d的元素。例如,若 x[]={3,7,2,4},y[]={1,5,2,3}, d 为 9;那么 x[1]+y[2]与 x[3]+y[1]都合乎条件,亦即都是 9。
【说明】
当然,一个初学者很可能会编写出如程序4-2所示的程序。
#define YES 1 #define NO 0 void sort(int [], int); int fix_sum(int x[], int y[], int m, int n, int given) { int first; int last; int middle; int i; sort(x, m); /* sort array x[] */ for (i = 0; i < n; i++) /* for each y[j], do a bin. */ for (first=0, last=m-1; first <= last; ) { middle = (first + last)/2; if (x[middle] + y[i] == given) return YES; else if (x[middle] + y[i] > given) last = middle - 1; else first = middle + 1; } return NO; } /* ------------------------------------------------------ */ #include <stdio.h> #include <stdlib.h> #include <string.h> void main(void) { int x[] = { 3, 7, 1, 2, 9, 4, 5}; int y[] = { 4, 2, 0, 3, 2, 7, 1, 9, 8}; int m = sizeof(x)/sizeof(int); int n = sizeof(y)/sizeof(int); int data, i; char line[100]; printf("\nFixed Sum Search Program"); printf("\n\nGiven Array #1 :"); for (i = 0; i < m; i++) printf("%4d", x[i]); printf("\n\nGiven Array #2 :"); for (i = 0; i < n; i++) printf("%4d", y[i]); printf("\n\nFixed Sum to be searched --> "); gets(line); data = atoi(line); if (fix_sum(x, y, m, n, data) == YES) printf("\nYES!, there is a pair summing up to %d", data); else printf("\nNO! no such sum exits"); }
#define NOT_FOUND -1 /* ------------------------------------------------------ */ /* function prototypes */ /* ------------------------------------------------------ */ void bound(int [], int, int *, int *); int search(int [], int, int, int); /* ------------------------------------------------------ */ /* FUNCTION inf_search : */ /* The control routine. */ /* ------------------------------------------------------ */ int inf_search(int x[], int GIVEN) { int left, right; bound(x, GIVEN, &left, &right); /* dound */ return search(x, GIVEN, left, right); /* then search*/ } /* ------------------------------------------------------ */ /* FUNCTION bound : */ /* Given a sorted infinite array and a key GIVEN, this */ /* function returns two subscripts, namely start and end, */ /* which bound the given key. */ /* ------------------------------------------------------ */ void bound(int x[], int GIVEN, int *start, int *end) { int delta = 1; /* interval length */ *start = 0; /* starting from the 1st pos*/ *end = *start + delta; /* interval ends before *end*/ while (!(x[*start] <= GIVEN && GIVEN < x[*end])) { delta += delta; /* if [start,end) can not */ *start = *end; /* bound, then double length*/ *end = *start+delta; /* and try again. */ } (*end)--; /* returns the true bound */ } /* ------------------------------------------------------ */ /* FUNCTION search : */ /* The traditional binary search function. */ /* ------------------------------------------------------ */ int search(int x[], int GIVEN, int low, int high) { int mid; while (low <= high) { mid = (low + high)/2; if (GIVEN < x[mid]) high = mid - 1; else if (GIVEN > x[mid]) low = mid + 1; else return mid; } return NOT_FOUND; } /* ------------------------------------------------------ */ #include <stdio.h> #include <stdlib.h> /* for atoi() */ #include <limits.h> /* for INT_MAX */ void main(void) { int number[30] = { 1, 3, 5, 8, 10, 21, 25, 50, 67, 68, 70, 84, 100, 130, 150, 151, 170, 180, 200, 300, 459, 480, 499, 503, 555, 570, 623, 699, 784, 981}; int input[100]; int i, key, answer; char line[100]; for (i = 0; i < 30; i++) input[i] = number[i]; for (i = 30; i < 100; i++) input[i] = INT_MAX; printf("\nInfinite Search Program"); printf("\n======================="); printf("\n\nGiven Infinite Sorted Array :"); for (i = 0; i < 100; i++) { if (i % 15 == 0) printf("\n"); if (input[i] < INT_MAX) printf("%4d", input[i]); else printf(" inf"); } printf("\n\nYour Search Key Please --> "); gets(line); key = atoi(line); if ((answer = inf_search(input, key)) >= 0) printf("\nKey found at position %d", answer); else printf("\nKey NOT FOUND!"); }
int cyclic_min(int x[], int n) { int left = 0; int right = n - 1; int mid; while (left < right) { /* if there is a gap : */ mid = (left + right)/2; /* get the middle item */ if (x[mid] < x[right]) /* if < the right most */ right = mid; /* then chop right part*/ else /* if >= the left part */ left = mid + 1; /* then chop right part*/ } return left; /* answer is the item */ } /* ------------------------------------------------------ */ #include <stdio.h> void main(void) { int x[] = { 20, 23, 28, 35, 39, 40, 42, 8, 10, 15, 17, 19}; int n = sizeof(x)/sizeof(int); int loc, i; printf("\nFind Cyclic Minimum"); printf("\n==================="); printf("\n\nGiven Array Sorted in Cyclic Fashion :\n"); for (i = 0; i < n; i++) printf("%3d", x[i]); loc = cyclic_min(x, n); printf("\n\nMinimum is located at x[%d] = %d", loc, x[loc]); }
void sort(int [], int); int median(int x[], int y[], int n) { int first_X = 0; /* lower element of x[] */ int first_Y = 0; /* lower element of y[] */ int last_X = n-1; /* higher element of x[] */ int last_Y = n-1; /* higher element of y[] */ int count = 0; /* # of smaller items elim. */ int mid_X, mid_Y; /* middle element pointers */ int number; /* # of elements left */ int z[4]; /* working array */ while ((last_X - first_X > 1) || (last_Y - first_Y > 1)) { mid_X = (first_X + last_X)/2; /* get mid ptrs */ mid_Y = (first_Y + last_Y)/2; if (x[mid_X] <= y[mid_Y]) { count += (mid_X - first_X); /* inc. count*/ first_X = mid_X; /* elim. lower half x[] */ last_Y = mid_Y; /* elim. higher half x[] */ } else { count += (mid_Y - first_Y); first_Y = mid_Y; /* elim. lower half y[] */ last_X = mid_X; /* elim. higher half x[] */ } } for (number = 0; first_X <= last_X; first_X++) z[number++] = x[first_X]; /* collect remainder */ for ( ; first_Y <= last_Y; first_Y++) z[number++] = y[first_Y]; sort(z, number); /* sort them */ return z[n-count-1]; /* pick up appropriate item */ } /* ------------------------------------------------------ */ /* FUNCTION sort : */ /* Special routine to sort small arrays with 2, 3 and */ /* 4 elements. */ /* ------------------------------------------------------ */ #define SWAP(x, y) { temp = x; x = y; y = temp; } void sort(int z[], int n) { int temp; switch (n) { case 4 : if (z[0] >= z[3]) SWAP(z[0], z[3]); if (z[1] >= z[3]) SWAP(z[1], z[3]); if (z[2] >= z[3]) SWAP(z[2], z[3]); case 3 : if (z[0] >= z[2]) SWAP(z[0], z[2]); if (z[1] >= z[2]) SWAP(z[1], z[2]); case 2 : if (z[0] >= z[1]) SWAP(z[0], z[1]); } } /* ------------------------------------------------------ */ #include <stdio.h> void main(void) { int x[] = { 1, 3, 6, 7, 8, 9, 10}; int y[] = { 2, 4, 5, 11, 12, 13, 14}; int n = sizeof(x)/sizeof(int); int i; printf("\nMedian of Two Sorted Arrays"); printf("\n==========================="); printf("\n\nArray #1 Array #2"); printf( "\n-------- --------"); for (i = 0; i < n; i++) printf("\n%6d%13d", x[i], y[i]); printf("\n\nMedian is %d", median(x, y, n)); }
#define ERROR -1 int bolzano_search(int x[], int n, int key) { int low = 0; int high = n-1; int mid; if (key > x[n-1] || key < x[0]) /* reject illegal in */ return ERROR; while (low <= high) { /* simply a binary search */ mid = (low + high)/2; if (key > x[mid]) low = mid + 1; else if (key < x[mid]) high = mid - 1; else return mid; /* search succeeds always */ } } /* ------------------------------------------------------ */ #include <stdio.h> #include <stdlib.h> void main(void) { int x[] = { 1, 2, 3, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 5, 6, 7, 8 }; int n = sizeof(x)/sizeof(int); int key, answer, i; char line[100]; printf("\nBolzano Type Binary Search"); printf("\n=========================="); printf("\n\nThe Given Array :\n\n"); for (i = 0; i < n; i++) printf("%3d", x[i]); printf("\n\nWhat is the key to be searched --> "); gets(line); key = atoi(line); if ((answer = bolzano_search(x, n, key)) >= 0) printf("\nKey found at location %d", answer); else printf("\n*** Input error ***\n Should be in the range" " of %d and %d (the first and the last element)", x[0], x[n-1]); }
#define FOUND 1 #define NOT_FOUND 0 int search(int x[], int y[], int z[], int X, int Y, int Z, int *XX, int *YY, int *ZZ) { *XX = *YY = *ZZ = 0; while (*XX < X && *YY < Y && *ZZ < Z) if (x[*XX] < y[*YY]) (*XX)++; else if (y[*YY] < z[*ZZ]) (*YY)++; else if (z[*ZZ] < x[*XX]) (*ZZ)++; else return FOUND; return NOT_FOUND; }
#include <limits.h> void f_and_s(int [], int, int, int *, int *); void first_second(int x[], int n, int *first, int *second) { f_and_s(x, 0, n-1, first, second); } /* ------------------------------------------------------ */ /* FUNCTION f_and_s : */ /* This function accepts the input array x[] and the */ /* left and right bounds, then returns the smallest and */ /* the second smallest elements in this range by using */ /* divide-and-conquer method. */ /* ------------------------------------------------------ */ void f_and_s(int x[], int left, int right, int *f, int *s) { int mid; int F1, F2; /* returned smallest items */ int S1, S2; /* returned second smallest */ if (left > right) /* range empty ? */ *f = *s = INT_MAX; /* YES, return INT_MAX */ else if (left == right) /* exactly one item ? */ *f = x[left], *s = INT_MAX; /* return it and inf*/ else { mid = (left + right)/2; /* now cut from middle */ f_and_s(x, left, mid, &F1, &S1); /* left */ f_and_s(x, mid+1, right, &F2, &S2); /* right */ if (F1 < F2) /* pick 1st and 2nd items. */ *f = F1, *s = (S1 < F2) ? S1 : F2; else *f = F2, *s = (S2 < F1) ? S2 : F1; } }
#define MAXSIZE 10 /* matrix size */ typedef int MATRIX[MAXSIZE][MAXSIZE]; /* matrix type */ void matrix_search(MATRIX mat, int n, int key, int *index_x, int *index_y) { int i = 0, j = n-1; /* start from upper right */ for (*index_x = *index_y = -1; i < n && j >= 0; ) if (mat[i][j] < key)/* element too small ? */ i++; /* move down one row. */ else if (mat[i][j] > key) /* element to large ? */ j--; /* move left one column */ else { *index_x = i; /* found, record locations */ *index_y = j; return; /* and return */ } return; }
#include <stdio.h> /* for I/O functions */ #include <stdlib.h> /* for atoi() */ #include <math.h> /* for sqrt() */ void main(void) { int given; /* the given number */ int row, column; /* row and column indicators*/ int count; /* number of solutions */ char line[100]; printf("\nRepresenting a Given Number as the Sum of Two Squares"); printf("\n=====================================================\n"); printf("\nAn Integer Please ---> "); gets(line); given = atoi(line); printf("\nCount X Y"); printf("\n----- ----- -----"); row = 1; /* starts from far enough */ column = (int) (sqrt((double) given) + 0.5); count = 0; /* so solution yet */ while (row <= given && column > 0) /* scan down... */ if (row*row + column*column == given) { count++; printf("\n%5d%7d%7d", count, row, column); row++; column--; } else if (row*row + column*column > given) column--; else row++; if (count == 0) printf("\n\nSorry, NO ANSWER found."); else printf("\n\nThere are %d possible answers."); }
#define MAXSIZE 10 #define min(a,b,c) (((a) < (b)) ? ((a) < (c) ? (a) : (c)) \ : ((b) < (c) ? (b) : (c))) typedef int MATRIX[MAXSIZE][MAXSIZE]; void maxsquare(MATRIX x, int n, int key, int *row, int *column, int *width) { MATRIX size; /* a working matrix */ int i, j; /* working storages */ for (j = 0; j < n; j++) /* copy last row of matrix */ size[n-1][j] = x[n-1][j]; /* x[][] to size[][] */ for (i = n-2; i >= 0; i--) { /* process bottom-up */ size[i][n-1] = x[i][n-1]; /* copy i-th row and */ for (j = n-2; j >= 0; j--)/* update size value */ size[i][j] = (x[i][j] == key) ? 1 + min(size[i+1][j],size[i][j+1],size[i+1][j+1]) : 0; } *width = 0; /* assume width is zero */ for (i = 0; i < n; i++) /* scan size[] matrix for */ for (j = 0; j < n; j++) /* the maximum and the */ if (size[i][j] > *width) { /* cooresponding*/ *width = size[i][j]; /* locations. */ *row = i; *column = j; } } /* ------------------------------------------------------ */ #include <stdio.h> void main(void) { MATRIX x = { { 1, 1, 1, 0, 0, 0, 0, 0}, { 0, 1, 1, 1, 1, 0, 0, 0}, { 0, 0, 1, 1, 1, 1, 1, 0}, { 0, 0, 0, 1, 1, 1, 1, 1}, { 0, 1, 1, 1, 1, 1, 1, 1}, { 0, 1, 1, 1, 1, 0, 1, 1}, { 0, 0, 1, 1, 1, 0, 0, 0}, { 0, 0, 1, 1, 1, 1, 0, 0}}; int n = 8; int row, column, width, key = 1; printf("\nFind Maximum Size Square of Same Data"); printf("\n====================================="); printf("\n\nGiven Matrix : \n"); for (row = 0; row < n; row++) { for (column = 0; column < n; column++) printf("%2d", x[row][column]); printf("\n"); } printf("\nKey to be searched = %d", key); maxsquare(x, n, key, &row, &column, &width); printf("\nMaximum Square is located at x[%d][%d] with size %d", row, column, width); }
参考:
C语言明天精选百则 冼镜光著
发表评论
-
C#使用OleDb读取Excel,生成SQL语句
2013-06-27 15:47 9959C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10706C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7878C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11417最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5879题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3478在C# 调用Delegate.Create ... -
考题小记(希望能持续增加)
2013-04-03 16:11 0在一块黑板上将123456789重复50次得到450位数12 ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构,数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1545今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——终曲
2012-11-05 23:27 50第9章终 曲 W 闼题9.1等璗正负号段 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2318C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 3977C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——排列,组合与集合
2012-11-04 23:28 10733C语言名题精选百则—— ... -
C语言名题精选百则——数字问题
2012-11-04 23:23 0C语言名题精选百则 ... -
C语言名题精选百则——序曲
2012-11-04 23:02 2C语言名题精选百则—— ... -
基本技术——贪心法、分治法、动态规划三大神兵
2012-11-03 19:30 0基本技术——贪心法、分治法、动态规划三大神兵
相关推荐
二叉查找树的C语言实现,实现功能:插入、删除、查找。
查找课程设计——包括二叉树查找(C语言版)绝对无错的
数据结构(c语言版)题集答案——第九章_查找.doc
串的查找和替换 c语言版的代码 数据结构课程设计
如果两者相同,则return1;用数组下标0-25分别表示a-z字母,对应的每个下标对应的数组元素的值就是该字母在该词中出现的次数。part是一个将字符串中的单词剥离的函数;将敏感词从字符串中剥离出来,将输入的打乱每个...
数据结构——C语言描述第6章-查找.pptx
用c语言编写的酒店管理系统,有删除,增加,修改,等功能
《C语言及程序设计》实践参考——区号查询-附件资源
《数据结构——用C语言描述》以C语言为程序设计语言,采用系列式的叙述方式,引导读者循序渐进地掌握数组、链接表、栈和队列、树与森林、图和堆等不同的数据结构,并系统地介绍了查找和排序的各种实现方法。...
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
这是一个编译的简单实验 用的是lex编写 lex使用在网上查找
目的:要求熟练掌握C语言的基本知识和编辑技能; 基本掌握结构化程序设计的基本思路和方法。 要求:设计一个职工信息管理系统,使之能提供以下功能: 1、应提供一个界面来调用各个功能,调用界面和各个功能的操作...
折半查找的处理过程是:在一个数据已排好序的数组中,首先比较关键字与数组中间的元素,如果两者相等,则查找结束;如果前者比后者小,则要查找的数据必然在数组的前半部,此后只需在数组的前半部中继续折半查找;...
添加学生信息,删除学生信息,修改学生信息,查找学生信息,统计学生人数,学生 成绩排名,查看全部学生信息 2、学生管理系统 查找学生信息,统计学生人数,学生成绩排名,查看全部学生信息
本科C语言课程设计,超市商品库存管理系统(纯C语言,当时很笨,调用函数自己画的界面) 具体功能: 以某超市为研究对象,了解超市商品进出库管理的基本数据流程,能对超市商品进行日常维护(录入、删除、编辑修改)...
(2)查找功能:按照时间和书名查找需要的书籍,查找成功后可以修改记录的相关项。 (3)排序功能:按照多种关键码对所有的书籍进行排序,例如按照购买日期进行排序、按图书类别排序等。 (4)显示图书的信息。 (5...
歌手成绩查询,包括添加成绩,查找,打分,排名等功能
void BubbleSort (int array[], int n); void SelectSort (int array[], int n); void InsertSort (int array[], int n);...在排序后的数组array查找元素e,如果能查到该元素,返回该元素的下标,否则返回 -1。
编写顺序查找、二分查找程序(二选一);编写建立二叉排序树的程序;编写在二叉排序树上的查找、插入、删除结点的程序;编写二叉排序树中序输出的程序
要求:1、用C语言实现程序设计; 2、利用结构体数组、链表等实现学生信息表达、查询等,充分体现数据结构的知识; 3、系统的各个功能模块要求用函数的形式实现; 4、界面友好(良好的人机交互),程序要有注释。 5、...