代码编织梦想

C++ 算法篇 高精度-爱代码爱编程

第一章 高精度计算         利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。        高精度计算中需要处理好以下几个

C++算法篇 快速幂-爱代码爱编程

让我们先来思考一个问题:7的10次方,怎样算比较快? 方法1:最朴素的想法,7*7=49,49*7=343,... 一步一步算,共进行了9次乘法。 这样算无疑太慢了,尤其对计算机的CPU而言,每次运算只乘上一个个位数,无疑太屈才了。这时我们想到,也许可以拆分问题。 方法2:先算7的5次方,即7*7*7*7*7,再算它的平方,共进行了5次乘法。 但这

C++算法篇 十大经典排序算法-爱代码爱编程

排序算法是中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。 关于时间复杂度 平方阶 (O(n2)) 排序 各类简单排

C++ 算法篇 动态规划----状态压缩-爱代码爱编程

一、总述 状态压缩动态规划,就是我们俗称的状压DP,是利用计算机二进制的性质来描述状态的一种DP方式。 很多棋盘问题都运用到了状压,同时,状压也很经常和BFS及DP连用。 状压dp其实就是将状态压缩成2进制来保存 其特征就是看起来有点像搜索,每个格子的状态只有1或0 ,是另一类非常典型的动态规划 举个例子:有一个大小为n*n的农田,我们可以在任意处

C++ 算法篇 动态规划----背包之七 有依赖的背包问题-爱代码爱编程

有依赖的背包问题    1、金明的预算方案  NOIP 2006 提高组 第二题 题目描述: 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是

C++ 算法篇 动态规划----背包之六 分组背包-爱代码爱编程

分组背包 问题:   有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是c[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 算法:   这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k

C++ 算法篇 动态规划----背包之五 二维费用背包-爱代码爱编程

二维费用背包 二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为c[i]。 算法

C++ 算法篇 动态规划----背包之四 混合背包-爱代码爱编程

混合背包    如果将01背包、完全背包、多重背包混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢? 01背包与完全背包的混合   考虑到在01背包和完全背包中最后给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类物品可以取无限次,那么

C++ 算法篇 动态规划----背包之三 多重背包-爱代码爱编程

多重背包 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本算法:       这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]

C++ 算法篇 动态规划----背包之二 完全背包-爱代码爱编程

完全背包 问题:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。   基本思路:     这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取

C++ 算法篇 动态规划----区间动态规划-爱代码爱编程

区间动态规划的含义与模板解释 区间DP,其实求的就是一个区间内的最优值. 一般这种题目,在设置状态的时候,都可以设f[i][j]为区间i-j的最优值 而f[i][j]的最优值,这有两个小区间合并而来的,为了划分这两个更小的区间,我们则需用用一个循环变量k来枚举,而一般的状态转移方程便是: f[i][j] = max/min (f[i][j] , f[i

C++ 算法篇 递推算法习题答案-爱代码爱编程

例1、一个数字三角形 #include<iostream> using namespace std; int main() { int n,i,j,a[101][101]; cin>>n; for (i=1;i<=n;i++) for (j=1;j<=i;j++) cin>>a[i]

C++ 算法篇 递推-爱代码爱编程

 递推  “递推”是计算机解题的一种常用方法。利用“递推法”解题首先要分析归纳出“递推关系”。如经典的斐波那契数列问题,用 f (i)表示第 i 项的值,则 f (1) =0,f(2) =1,在 n>2 时,存在递推关系:f (n) = f(n-1) + f(n-2)。      在递推问题模型中,每个数据项都与它前面的若

C++ 算法篇 穷举(枚举)-爱代码爱编程

 穷举 计算机的特点之一就是运算速度快,善于重复做一件事。“穷举”正是基于这一特点的最古老的算法。它一般是在一时找不出解决问题的更好途径,即从数学上找不到求解的公式或规则时,根据问题中的“约束条件”,将解的所有可能情况一一列举出来,然后再逐个验证是否符合整个问题的求解要求,从而求得问题的可行解或者最优解。   一、 穷举算法的应用举例  

C++ 算法篇 深度优先搜索(DFS)习题答案-爱代码爱编程

1、瓷砖 #include<bits/stdc++.h> using namespace std; int a[51][51]={0},ans=0; void dfs(int x,int y) { ans++; a[x][y]=false; if(a[x-1][y]) dfs(x-1,y); if(a[x+1][y

C++ 算法篇 广度(宽度)优先搜索(BFS)习题答案-爱代码爱编程

宽度优先搜索是一种“盲目”搜索,所有结点的拓展都遵循“先进先出”的原则,所以采用“队列”来存储这些状态。宽度优先搜索的算法框架如下: 1、瓷砖 (queue写法) #include<bits/stdc++.h> using namespace std; int px[4]={0,0,1,-1}; int py[4]={1,

C++算法篇 递归调用(函数调用自身)-爱代码爱编程

要理解运用递归要学习理解下面几个问题: 什么是递归?  递归的精髓(思想)是什么?  递归和循环的区别是什么?  什么时候该用递归?  使用递归需要注意哪些问题?  递归思想解决的几个经典的问题?    1、递归概念: 德罗斯特效应就是说,你拿着一面镜子,然后再站在一面镜子前面,让两面镜子相对。你看到镜子里面的情景,是相同的,无限循环的。 在数

C++算法篇 二分算法-爱代码爱编程

一、二分法的基本思想:       二分法是一个非常高效的算法,它常常用于计算机的查找过程中。       先玩一个小游戏。预先给定一个小于100的正整数x,让你猜,猜测过程中给予大小判断的提示,问你怎样快速地猜出来?        这样猜测最快,先猜50,如果猜对了,结束;如果猜大了,往小的方向猜,再猜25;如果猜小了,往大的方向猜,再猜75;…,

C++算法篇 模拟算法-爱代码爱编程

1、P1059 明明的随机数   NOIP 2006 普及组 第一题 题目描述 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协

C++算法篇 贪心算法-爱代码爱编程

        实际生活中,经常需要求一些问题的“可行解”和“最优解”,这就是所谓的“最优化”问题。一般来说,每个最优化问题都包含一组“限制条件”和一个“目标函数”,符合限制条件的问题求解方案称为可行解,使目标函数取得最佳值(最大或最小)的可行解称为最优解。求解最优化问题的算法很多,例如穷举、搜索、动态规划等。贪心法也是求解这类问题的一种常用方法。 1.