practical_sharp的博客

今天博主复习了一下栈与递归的知识，做了计蒜客平台的一章习题。下面贴出来和大家交流分享。如有不正之处，请求指教。蒜头君吃桃题目描述思路分析设第i天还剩下g(n)个桃子 那么第i-1天还剩下g(n-1)个桃子。根据递推关系 有：g(n-1) = g(n) - g(n)/2 - 1 所以 g(n) = 2(g(n-1) + 1)第一天还剩下1个桃子 所以g(1) = 1那么可以写出...

首先附上题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5667题目分析像这种递推公式的问题，n很大的时候，常用的处理方法是矩阵快速幂，但是这个好像很难构造。博主思路如下：取对数 设k(i) = loga(f(i))那么 根据推导k(1) = loga(1)=0k(2) = loga(ab) = bk(i) = b + c*k(i-...

题目来源http://acm.hdu.edu.cn/showproblem.php?pid=3351问题描述我没有故事了。多年来，我一直在写故事，有些故事很愚蠢，只是为了使简单的问题看起来很难而复杂的问题看起来很容易。通过打开和关闭大括号，将获得一个完整的非空字符串。您的任务是找到使字符串稳定所需的最少“操作”数。稳定的定义如下：1.空字符串是稳定的。2.如果S稳定，则{S}也稳定。...

Description从输入中读取一个数n，求出n！中末尾0的个数。Input输入有若干行。第一行上有一个整数m，指明接下来的数字的个数。然后是m行，每一行包含一个确定的正整数n，1<=n<=1000000000。Output对输入行中的每一个数据n，输出一行，其内容是n！中末尾0的个数。Sample Input331001024Sample Output02...

笔者总结自己的思路，有以下两种方法解决求幂的长度，求阶乘的长度。从而解决形如“请你计算数a的b次幂共有多少位(十进制的数)!”“N! (N的阶乘) 是非常大的数，计算公式为：N! = N * (N - 1) * (N - 2) * … * 2 * 1)。现在需要知道N!有多少（十进制）位。”之类的问题。方法一：调用log10()函数解决阶乘的位数int digit(int n)//求数n...

今天在一个网站上刷题，这个网站很有趣。https://projecteuler.net这个网站是纯英文网站，需要注册，登陆。接下来，博主开启欧拉五十讲的刷题之旅啦。Problem 1：Multiples of 3 and 5If we list all the natural numbers below 10 that are multiples of 3 or5, we get ...

编程需要相当扎实的数学基础。今天笔者要复习的是关于两个数的最大公约数和最小公倍数的问题，同时会收录一些习题进行练习。最大公约数和最大公倍数的定义最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法...

问题描述设m是一个正整数，现在要求将n分解为若干个互不相同的自然数的和，且使得这些自然数的乘积最大。注意：这个问题不同于剪绳子问题，因为剪绳子问题可以使得每一段重复相等，而此问题必须使得划分出来的每一个数都互斥。算法设计对于给定的正整数m，要求计算最优分解方案数据输入输入只有1行，表示整数m输入样例1：10输入样例2：100数据输出输出有两行第一行表示整数m划分的各个自然...

问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。解空间解空间：排列树x=[1 2 3……n]相应的排列树由x[1:n]的所有排列构成思路旅行商问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1,2，3…n的所有排列的递归算法Perm相似。初始的时候x=[1,2,3,…...

问题描述给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。连通图的可着色问题给定图G=(V,E)和m重颜色，若这个图不是m可着色，...

问题描述

问题描述思路回溯法求解，解空间是一棵子集树。算法的时间复杂度为O(2n)代码#include <iostream>using namespace std;#include<stdio.h>#include<stdlib.h>#include<cstring>#include<math.h>int bestv=0;/...

问题描述印刷电路板将布线区域划分成n*m个方格阵列，精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线问题。在布线时，电路只能沿着直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。问题分析布线问题的解空间是一个图结构。解决的思路采用分支限界法，从起始节点开始不断扩展，直到目的节点结束，得到最短的路径长度(即最优值)；然后从目的节点...

问题描述给你一根长度为N的绳子，请把绳子剪成M段（m,n都是整数），每段绳子的长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2] …的乘积最大约定：剪出来的每段小绳子也必须为整数例如 绳子长度8 剪成3段 最大乘积18 = 2*3 *3输入输入只有1行，分别为N，M；其中N表示绳子的长度，M表示要剪成的段数。0<=N<=10000...

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。物品i12345重量w[i]3024103540//Sort函数的目的是将集装箱的序号按照集装箱重量从小到大排序vo...

题目有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。思路具有最优子结构性质和贪心选择性质。只要是所有物品的总重量大于背包容纳量，那么背包一定能装满。注意背包问题与0-1背包问题的区别。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。求解步骤用...

题目描述： 有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？根据m[i][j]的递推公式，背包中最大的价值总和为m[1][n]#include <iostream>#include<stdio.h>#include<std...

设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。如上图，所列出的正方形表是8个选手...

基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合//三个指针实现归并排序void merge(int a[],int l,int r,int mid){ int temp[r-l+1],i,j,k; i=l;//左半部分指针 j=mid+1;//右半部分指针 //k是临时数组指针 k=0;//...

棋盘覆盖问题描述在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。求解思路当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个...

设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm( R) = ( r )，其中r是集合R中唯一的元素； 当n>1时，perm(...

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。问题描述设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起...

问题描述若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是...

问题如下：采用递归分治法，类似于二分查找，找左边最大值和右边最大值，然后比较，返回比较大的那一个。递归的出口是当左下标>=右下标时，返回当前元素。例：if(i>=j) return a[i];不多说了，思路比较简单，直接堆代码#include <iostream>#include<stdlib.h>#include<string.h>u...

最大子段和问题问题描述如下：多重循环求解问题的核心是求解连续的一段子序列使其和最大。最容易想到的便是通过循环遍历寻找最优的下标i，j使得a[i]+…+a[j]的和最大。很容易看出时间复杂度为O(n^3)。#include <iostream>#include<stdlib.h>#include<stdio.h>using namespace st...

小明种苹果（apple）【题目描述】小明在他的果园里种了一些苹果树。为了保证苹果的品质，在种植过程中要进行若干轮疏果操作，也就是提前从树上把不好的苹果去掉。第一轮疏果操作开始前，小明记录了每棵树上苹果的个数。每轮疏果操作时，小明都记录了从每棵树上去掉的苹果个数。在最后一轮疏果操作结束后，请帮助小明统计相关的信息。【输入格式】从标准输入读入数据。第 1 行包含两个正整数 N 和 M，分别表...

Input：输入两行标准输入，第一行表示矩阵的个数，第二行是这些矩阵的维数。Output：输出两行标准输出，第一行为这些矩阵的最小数乘次数，第二行为这些矩阵加括号后的表达式。输入样例1：630 35 15 5 10 20 25输出样例1：15125((A1(A2A3))((A4A5)A6))具体使用的数据结构：输入n表示矩阵的个数int *p = new int[n+1]用来表...