算法练习：最长平台问题

2016年07月27日 36 阅读

算法练习：最长平台问题2015-02-15内容：一直一个已经从小到大排序的数组，这个数组中的一个平台就是连续的一串相同的元素，并且这个元素不能再延伸。例如，在1,2,2,3,3,3,4,5,5,6中1,2,2,3,3,3,4,5,5,6都是平台.试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在这个例子中, 3,3,3就是该数组的中的最长的平台。说明：这个程序十分简单，但是编写好却不容易，因此在编写程序时应注意考虑下面几点：1.使用变量越少越好...

算法练习：支配值数目

2016年07月27日 34 阅读

算法练习：支配值数目2015-02-15内容：已知f[]和g[]两个整数数组，元素都已经从小到大排列，试编写程序算出f[]中每一个元素比g[]中每一个元素大的个数的总数。换句话说，f[0]比g[]中多少个元素大、f[1]比g[]中多少个元素大，这些值得总和就是所要求的答案。例如，如果f[]中有1,3,5,7,9，而g[]中有2,4,6,7,8，比g[0]大的有f[1]~f[4],比g[1]大的有f[2]~f[4],比g[2]大的有f[2]~f[4],比g[...

算法练习：等值数目

2016年07月27日 36 阅读

算法练习：等值数目2015-02-15内容：已知两个整数数组f[]与g[]，它们的元素都已经从小到大排列好，而且两个数组中的元素都各不相同。例如，f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。就上例而言，f[2]和g[1]为3是一组；f[4]和g[3]为8是一组。所以共有两组。经过了前两天的编写，我觉得程序不具有代表性，所以我打算以后把核心算法的部分写出函数的形式，这样看起来更直观。我的解法...

算法练习：数组的距离

2016年07月27日 33 阅读

算法练习：数组的距离2015-02-15内容：已知两个元素从小到大排列数组x[]和y[]，请编写一个程序算出两个数组元素彼此之间差的绝度值中最小的一个数，此值称作数组的距离。例如:x[]有1,3,5,7,9 y[]有2,6,8 那么最短距离就是1，因为x[0]和y[0]、x[1]和y[0]、x[2]和y[1]、x[3]和y[1]还有x[4]和y[2]的距离都是1.我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就...

算法练习：Armstrong数

2016年07月27日 33 阅读

算法练习：Armstrong数2015-02-15内容：在三位的正整数中，例如abc，有一些可以满足a^3+b^3+c^3=abc的条件，也就是说各个位数的立方和正好是该数本身，这些数称为Armstrong数。是编写一个程序求出所有的三位Armstrong数。我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！Armstrong数在国内好像就叫做水仙花数，很多程序设计的课本后面都有这种类型的思考题，确实很简单...

算法练习：等值首尾和

2016年07月27日 39 阅读

算法练习：等值首尾和2015-02-15内容假设有一个数组x[],它有n个元素，每一个都大于零；称x[0]+x[1]+...+x[i]为前置和,而x[j]+x[j+1]+...+x[n-1]为后置和。试编写一个程序，求出x[]中有多少组相同的前置和后置和。例如：x[]的元素是3,6,2,1,4,5,2，于是x[]的前置和有以下7个，即3,9,11,12,16,21,23；后置和则2,7,11,12,14,20,23;于是11,12,23,这3对就是值相同的...

通过指针对字符串进行查询并且替换其中的指定字符

2016年07月27日 32 阅读

通过指针对字符串进行查询并且替换其中的指定字符2015-02-17#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>//有一个字符串符合以下特征（” "abcd11111abcd2222abcdqqqqq"”）, 要求写一个函数（接口），输出以下结果//求字符串...

动态规划法：背包问题

2016年07月27日 35 阅读

动态规划法：背包问题2015-02-17一 几个概念：最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不止一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值的可行解成为最优解，这类问题称为最优化问题。二 最优性原理：对于一个具有n个输入的最优化问题，其求解的...

如何求n阶方阵中各条反斜线上的元素之和4*4

2016年07月27日 38 阅读

如何求n阶方阵中各条反斜线上的元素之和4*42015-02-17#include<stdio.h>void main（）{//其中第一条斜线是00 - 11 - 22 -33 第二条10 - 21 - 32int arr2[4][4] = { 00,01, 02, 03,10 ,11, 12, 13, 20 ,21, 22, 23,30, 31, 32, 33,};int i, j;int sum = 0;int index = 0;for （...

如何判断完数然后输出6=1+2+3 28=1+2+4+7+14

2016年07月27日 36 阅读

如何判断完数然后输出6=1+2+3 28=1+2+4+7+142015-02-17#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<math.h>int f（int num）{int index = 0;int sum=0;int a[50];for （int i = 1; i < num; i++）{if （num%i == 0）{a[index] = i;in...

通过质数的判断然后随机的找到一个偶数等于两个素数的和

2016年07月27日 36 阅读

通过质数的判断然后随机的找到一个偶数等于两个素数的和2015-02-17#include<stdio.h> #include<math.h> int zhi（int num） { int m = sqrt（num）; for （int i = 2; i <= m; i++） { if （num%i == 0） return 0; } return 1; } void qh（int num）{ //m是i所能达到的最大值 怎样求...

哈希法判断两个有根树是否同构

2016年07月27日 37 阅读

哈希法判断两个有根树是否同构2015-02-17DescriptionSome major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique cent...

买彩票问题

2016年07月27日 34 阅读

买彩票问题2015-02-17Problem StatementIn most states, gamblers can choose from a wide variety of different lottery games. The rules of a lottery are defined by two integers （choices and blanks） and two boolean variables （sorted and uniq...

爬山问题

2016年07月27日 35 阅读

爬山问题2015-02-17Problem StatementA hiker has set out to conquer a hill. The trail guide for the hill lists information known about the hill. First, it lists how tall the hill is, and how far it is to the other side of the hill. Next...

树上三角形解决RE Runtime Error

2016年07月27日 38 阅读

树上三角形解决RE Runtime Error2015-02-17时间限制:4000ms单点时限:2000ms内存限制:256MB描述有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？输入输入数据的第一行包含一个整数 T，表示数据组数。接下来有 T 组数据，每组...

计算任意一个图生成树的个数:Kirchhoff 的Matrix Tree方法Java实现

2016年07月27日 42 阅读

计算任意一个图生成树的个数:Kirchhoff 的Matrix Tree方法Java实现2015-02-17计算任意一个图的生成树的个数，是Kirchhoff提出的理论，通常称为Matrix Tree Theorem，原理很简单：Let G be a graph with V（G）={v1,v2,...,vn},let A={aij}be the adjacentcy matrix of G,and let C={cij}be the n*n matrix...

最小生成树算法：Kruskal算法的Java实现

2016年07月27日 37 阅读

最小生成树算法：Kruskal算法的Java实现2015-02-17闲来无事，写个算法，最小生成树的Kruskal算法，相对比Prim算法实现起来麻烦一点点package trees;import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.PriorityQueue;import java.util.Set;/*** 最小生成树的Krus...

强连通分支算法概述

2016年07月27日 35 阅读

强连通分支算法概述2015-02-17深度优先搜索有一种经典的应用：把一个有向图分解为各强连通分支。很多有关有向图的算法都是从这种步骤开始的。（算法导论P338，觉得简洁而精妙，分享下）STRONGLY-CONNECTED-COMPONENTS（G）1 call DFS（G） to compute finishing times f[u] for each vertex u2 compute GT3 call DFS（GT）. but in the mai...

CSU 1414: Query on a Tree

2016年07月27日 30 阅读

CSU 1414: Query on a Tree2015-02-17预处理每个结点的子结点的个数sons , 则对x的询问可由sons[x]- sigma（ sons[v] ） （v是到x距离为d的点）得到怎么快速的找到这些v呢？ 注意到距离x为d的点肯定在树的同一层....可以对树进行dfs时记录每个结点时间戳的同时把每一层的结点保存下来,然后对每一层维护一个前缀和 如果v是x下面子结点那么v的时间戳肯定在x的范围内,这样就可以二分確定出前缀和的范围了...

迷宫问题的研究与实现

2016年07月27日 35 阅读

迷宫问题的研究与实现2015-02-17【问题描述】以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（1）根据二维数组，输出迷宫的图形。（2）探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。【算法分析】主要考查数据结构-栈。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它...