- 博客(92)
- 收藏
- 关注
RSS订阅原创 线性时间选择——选择第k个数
线性时间选择——选择第k小的数 采用的算法思想和快速排序十分相似，选取基准进行一次快排，得到一个基准和左侧小于基准右侧大于基准的数组。然后判断基准的位置，如果第k个数在左边便接着向左递归，如果在右侧便接着向右侧递归。程序实现#include<iostream>#include<set>#include<cmath>#include<vector>#include<map>#include<string>#includ
2021-05-01 10:31:49
395
原创 快速排序
快速排序算法 快速排序的算法思想就是每一次选取一个元素，然后以此元素为基准，将大于基准的元素放到基准的后面，将小于基准的元素放到基准的前面，然后递归下去直到只有他自己为止。平均算法时间复杂性为O（nlogn）。由于有时候会遇到数组的大部分是符合降序排序的，这样就会大大影响时间复杂性。因此，再程序中采取一个随机数来作为基准。程序实现#include<iostream>#include<set>#include<cmath>#include<vector&
2021-05-01 10:07:50
124
原创 斐波那切数列算法
递归普通算法//斐波那切数列的递归算法template <typename Type>Type fibonacci_1(int n,Type flag){ if(n<=1)return 1; return fibonacci_1(n-1,flag)+fibonacci_1(n-2,flag);}递归免重复计算算法//斐波那切数列——保存以计算的值template <typename Type>Type fibonacci_4(int n,Ty
2021-04-29 17:43:21
243
原创 线性规划——产销平衡
运输问题（产销平衡） 某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？ 解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为显然是一个线性规划问题，当然可以用单纯形法求解。 对产销平衡的运输问题，由于有以下关系式存在：其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由
2021-04-26 17:14:19
4426
3
原创 matlab线性规划
线性规划问题 在一组线性约束条件下的限制下，求一线性目标函数最大或最小的问题。线性规划标准型数学标准型：可行解：满足约束条件的解矩阵x=[x1,x2,x3,…,xn]。最优解：是目标函数达到最大值或者最小值的可行解。可行域：所有可行解构成的集合称为问题的可行解，记为R。matlab标准型：f,x,b,beq,lb,ub为列向量f称为价值向量b称为资源向量A，Aeq为矩阵Matlab线性规划函数——linprog>> help linproglinpr
2021-04-23 19:38:13
2752
1
原创 按照字典顺序打印一个数的全排列
输入一个数n，按照字典顺序从小到大打印出(1-n)的全排列。两个序列的字典序大小关系等价于从头开始第一个不相同位置处的大小关系。Input正整数n(1<=n<=7)。Output按照字典顺序从大到小打印全排列。每个样例之间有一个空格Sample Input1234Output1121 22 131 2 31 3 22 1 32 3 13 1 23 2 141 2 3 41 2 4 31 3 2 41 3 4 21 4 2 31 4
2021-03-01 21:19:33
680
原创 Prime Ring Problem UVA - 524
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1*,2,…,n* into each circle separately, and the sum of numbers in two adjacent circles should be a prime.Note: the number of first circle should always be 1.Inputn (0
2021-03-01 20:07:57
885
原创 Knight Moves UVA - 439
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part
2021-02-18 19:15:08
120
原创 Tree Recovery UVA - 536
Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. This is an example of one of her creations:To record her trees for future generations, she wro
2021-02-17 18:01:47
83
原创 S-Trees UVA - 712
A Strange Tree (S-tree) over the variable set Xn = {x1*,x2,…,xn*} is a binary tree representing a Boolean function f : {0*,1}n → {0,*1}. Each path of the S-tree begins at the root node and consists of n + 1 nodes. Each of the S-tree’s nodes has a depth,
2021-02-17 18:00:49
136
原创 Parentheses Balance UVA - 673
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:(a) if it is the empty string(b) if A and B are correct, AB is correct,© if A is correct, (A ) and [A ] is correct.Write a program that takes a se
2021-02-17 17:59:23
78
原创 Updating a Dictionary UVA - 12504
In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.Each dictionary is formatting as follows:{ke
2021-02-15 17:30:19
90
1
原创 Searching the Web UVA - 1597
The word “search engine” may not be strange to you. Generally speaking, a search engine searches the web pages available in the Internet, extracts and organizes the information and responds to users’ queries with the most relevant pages. World famous sea
2021-02-15 16:12:28
122
原创 Bug Hunt UVA - 1596
In this problem, we consider a simple programming language that has only declarations of onedimensional integer arrays and assignment statements. The problem is to find a bug in the given program. The syntax of this language is given in BNF as follows:
2021-02-14 16:58:07
171
原创 Ancient Messages UVA - 1103
In order to understand early civilizations, archaeologists often study texts written in ancient languages. One such language, used in Egypt more than 3000 years ago, is based on characters called hieroglyphs. Figure C.1 shows six hieroglyphs and their name
2021-02-13 17:56:16
127
原创 深度优先遍历
算法思想 图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。代码实现邻接矩阵实现：结构体定义：使用二维数组来定义，存入一个结构体中，记录顶点个数。演示是无向图的邻接矩阵#define MAX 10struct MGraph{ int arr[MAX][MAX]; //存储图的连通状态：1为连通，0为非连通
2021-02-09 22:04:54
105
原创 Quadtrees UVA - 297
A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represent
2021-02-09 20:41:50
112
原创 Oil Deposits UVA - 572
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each
2021-02-09 20:39:58
93
原创 Not so Mobile UVA - 839
Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies. The figure illustrates a simple mobile. It
2021-02-09 12:51:18
90
原创 The Falling Leaves UVA - 699
Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened to binary trees, how large would the piles of l
2021-02-09 12:49:49
91
原创 Tree UVA - 548
You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.Input The input f
2021-02-09 12:48:59
64
原创 Trees on the level UVA - 122
Trees are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer gr
2021-02-09 12:43:26
75
原创 Trees on the level UVA - 122
Trees are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer gr
2021-02-07 16:14:14
243
原创 Dropping Balls UVA - 679
A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path
2021-02-06 19:35:57
86
原创 Matrix Chain Multiplication UVA - 442
Suppose you have to evaluate an expression like ABCDE where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed stro
2021-02-06 18:59:46
82
原创 Borrowers UVA - 230
I mean your borrowers of books — those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes.– (Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’) Like Mr. Lamb, librarians have their problems with borrow
2021-02-06 17:09:25
79
原创 Boxes in a Line UVA - 12657
You have n boxes in a line on the table numbered 1*…n* from left to right. Your task is to simulate 4 kinds of commands:• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )• 2 X Y : move box X to the right to Y (ignore t
2021-02-06 17:08:14
62
原创 Broken Keyboard (a.k.a. Beiju Text) UVA - 11988
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed(internally).You’re not aware of this issue, since you’re focu
2021-02-06 17:07:05
58
原创 Rails UVA - 514
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out
2021-02-06 17:06:08
73
原创 Broken Keyboard (a.k.a. Beiju Text) UVA - 11988
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed(internally).You’re not aware of this issue, since you’re focu
2021-02-05 17:49:02
392
原创 Boxes in a Line UVA - 12657
You have n boxes in a line on the table numbered 1*…n* from left to right. Your task is to simulate 4 kinds of commands:• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )• 2 X Y : move box X to the right to Y (ignore t
2021-02-05 17:48:32
64
原创 Printer Queue UVA - 12100
The only printer in the computer science students’ union is experiencing an extremely heavy workload. Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output.Because some jobs are more impo
2021-02-03 11:18:28
99
原创 C++ 内存模型之单独编译
单独编译得意义将一个程序分成多个文件按保存，如果过对程序修改，找到要修改得文件进行修改后重新编译，则可以之重新编译该文件，然后后将他于其他文件得编译版本链接，是的大程序得管理更加高效便捷。将单文件里面得完整程序进行分开一般单文件大程序可以分成三部分。头文件：包含结构声明和使用这些结构得函数原型。函数原型使用#define或const定义得符号常量结构声明类声明模板声明内联函数源代码文件：包含于结构有关得函数得代码。源代码文件：包含调用于结构相关得函数得代码。注意：不要将函
2021-02-02 17:01:30
103
原创 C++ new和delete运算符得简单使用
NEWC++ 中的new运算符用来分配内存，和c语言中得malloc有相似得功能。使用new为当个元素开辟内存空间,并返回地址typeName *pointer_name =new typeName;例如：使用new开辟可以存储int类型数值大小得内存空间，然后返回开辟得内存空间得地址。int *a=new int;使用new创建动态数组并返回地址typeName *pointer_name =new typeName[size];例如：使用new来创建包含10个int元素得数
2021-02-02 15:21:03
139
原创 Symmetry UVA - 1595
The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is
2021-02-02 14:51:52
90
原创 Compound Words UVA - 10391
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.Input Standard input consists of a number of lowercase words,
2021-02-02 11:11:10
137
原创 C++ 函数模板
函数模板时通用的函数描述，他们使用泛型来定义函数，其中的泛型可以用具体的类型代替。将类型作为参数传递给模板，编译器可以生成该类型的函数。模板建立//examplestemplate <typename AnyType> void Swap(AnyType& a, AnyType& b){ AnyType temp; temp = a; a = b; b = temp;}//调用方式int main(){ int a=32; i
2021-02-01 21:50:16
53
原创 Foreign Exchange UVA - 10763
Your non-profit organization (iCORE - international Confederation of Revolver Enthusiasts) coordinates a very successful foreign student exchange program. Over the last few years, demand has sky-rocketed and now you need assistance with your task. The
2021-02-01 19:08:24
76
原创 Ducci Sequence UVA - 1594
A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a1*,a2,···,an*), the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:(a1*,a2,···,an*) → (|a1 − a2|,|a2 − a3|,···,|an
2021-02-01 17:16:24
170
原创 Throwing cards away I UVA - 10935
Given is an ordered deck of n cards numbered 1 to n with card 1 at the top and card n at the bottom. The following operation is performed as long as there are at least two cards in the deck: Throw away the top card and move the card that is now on the
2021-02-01 16:29:07
101
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人