- 浏览: 147253 次
- 性别:
- 来自: 帝都
文章分类
最新评论
-
jackchen0227:
汗,谢谢啊
joj 1817: Triangle 三角形的判定 -
RootJ:
输出时候没有写:号。。。
joj 1817: Triangle 三角形的判定 -
jackchen0227:
嗯再捡捡。。
不带括号的四则运算 -
ruby_windy:
不是大二实验课写的么...
不带括号的四则运算
转自网易何国涛的博客http://zhedahht.blog.163.com/blog/static/25411174200732711051101/
题目:输入一个正数n,输出所有和为n连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
分析:这是网易的一道面试题。
这道题和本面试题系列的第10题有些类似。我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1,big初始化为2。如果从small到big的序列的和大于n的话,我们向右移动small,相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话,我们向右移动big,相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2,因为序列至少要有两个数字。
基于这个思路,我们可以写出如下代码:
void PrintContinuousSequence(int small, int big); ///////////////////////////////////////////////////////////////////////// // Find continuous sequence, whose sum is n ///////////////////////////////////////////////////////////////////////// void FindContinuousSequence(int n) { if(n < 3) return; int small = 1; int big = 2; int middle = (1 + n) / 2; int sum = small + big; while(small < middle) { // we are lucky and find the sequence if(sum == n) PrintContinuousSequence(small, big); // if the current sum is greater than n, // move small forward while(sum > n) { sum -= small; small ++; // we are lucky and find the sequence if(sum == n) PrintContinuousSequence(small, big); } // move big forward big ++; sum += big; } } ///////////////////////////////////////////////////////////////////////// // Print continuous sequence between small and big ///////////////////////////////////////////////////////////////////////// void PrintContinuousSequence(int small, int big) { for(int i = small; i <= big; ++ i) printf("%d ", i); printf("\n"); }
上面的题目和本题目有类似之处,但是要求子序列是连续的整数。。。
/* 题意: 将数字N分成2份以上.使用的数字不可重复.例如5=1+4=2+3,就只有两种拆分的方式.输入:每一行给出一个数字N,3<=N<=500.整个测试以0代表结束. 方法1,动态规划 这道题只要求计数,我们考虑是否能用递推、DP、组合数学的方法解决。 如果不理会题目中要求阶梯数不能为1的条件(即不能用自己组成自己), 那么这道题要求的实际上就是从1,2,3,...,n这个正整数序列中选数来组成n的种类数,我们最后只要减去1(就是用自己组成自己的那一种)就行。 设f[a,b]表示用正整数序列中前b个数组成a的种类数,我们以b为阶段进行计算。添加上第b个正整数(也就是b)后,我们可以用b来组成a,也可以不用b, 于是就有f[a,b]=f[a-b,b-1]+f[a,b-1]。 对于边界条件,我们考虑,很明显有f[1,1]=1,而f[1,1]=f[1-1,1-1]=f[0,0]=1,所以边界条件为f[0,0]=1。 注意到第b阶段只和第b-1阶段有关,所以可以省掉b维,只需要用两个数组f0,f1滚存,f0存第b-1阶段,f1存第b阶段,就可以了,初始状态为f0[0]=1。 又观察到计算f1[a]时,只与f0中比a小的状态有关,于是可以采取将a从大到小计算,这样只需要用一个数组就可以解决问题了。 这道题如果用搜索, 肯定爆TLE没救。由于题目的结果比较大,得用Extended来存贮。如果用另一种二维DP,会爆MLE,用这种一维DP则不会 方法2:生成函数法(其实就是 仅使用一维状态 的dp ) 计算(1+x)(1+x^2)(1+x^3)-----,x^n的系数即为所求 int i,j; double ans[510]={1,1};//已经把ans[1]和ans[0]赋为1了,其余为0 for(i=2;i<=500;i++) { for(j=500;j>=0;j--) //逆序 { if(i+j<=500) ans[i+j]+=ans[j]; } } 先计算(1+x)(1+x^2) 再计算(1+x)(1+x^2) *(1+x^3) */ #include<iostream> #include<cstdlib> using namespace std; double dp[501][501]={0}; //这个为动态规划使用 /* 使用二维状态的 dp */ int dpBasic(int num) { dp[0][0] = 1; /* dp[0][1] = dp[1][0] = 0; for(int k=1;k<=500;k++) dp[k][1] = 1; for(int i=0;i<=500;i++) //i 从 0开始 { for(int j=1;j<=i;j++) //由于 j - 1 的存在 所以 下界 1 dp[i][j] = dp[i-j][j-1] + dp[i][j-1]; }*/ int i,k; for(i = 0; i < 501; i ++) { for(k = 1; k <= i; k ++) dp[i][k] = dp[i - k][k - 1] + dp[i][k - 1]; for(k = i + 1; k < 501; k ++)//k > i时候 dp[i][k] = dp[i][i],这些是必须的,因为防止后面的计算需要这些东西 dp[i][k] = dp[i][i]; } return dp[num][num] -1; } /* 仅适用一维的动态规划 注意: 转成一维的时候,注意必用一个逆循环,为什么是不是正循环 */ double inta[502] ; // int 时 wrong answer,此处使用一维 int dpAd(int num) { int i , j; int n ; inta[0] = 1 ; for ( i =1 ;i <= 500 ;i++ ) for( j =500 ;j >= i ;j -- ) //此处是逆循环 inta[j] += inta[j-i] ; return inta[num] - 1; } int main() { while(scanf("%d",&n),n) { printf("%d\n",dpBasic(n)); } return 0; }
发表评论
-
-在二元树中找出和为某一值的所有路径--捡捡递归的使用
2012-03-30 21:05 933/* 算法要求:打印从root到叶节点的路径上的权值和 为 ... -
不带括号的四则运算
2011-10-09 21:24 1482/* 不带括号的表达式的四则运算 使用两个堆栈,一个o ... -
[zz]catalan数的分析与应用
2011-06-25 22:09 1380性质 令h(0)=1,h( ... -
joj 1085: I Think I Need a Houseboat 半圆形侵蚀
2011-06-24 20:54 9831085: I Think I Need a Ho ... -
joj 1032 deck 重心的计算
2011-06-24 19:12 11361032: Deck Result TIME ... -
joj 1186 Box of Bricks 水题
2011-06-19 09:46 9641186: Box of Bricks Re ... -
joj 1062 Computer Versus Mankind 非递归最大公约数 最小公倍数
2011-06-18 15:15 12501062: Computer Versus Mankin ... -
基本的排序:非递归的堆排序
2011-06-17 15:38 0void restore(int root,int le ... -
joj 1817: Triangle 三角形的判定
2011-06-15 20:34 13491817: Triangle Result ... -
×joj 1175 The Binomial Function 递归,递归优化,非递归
2011-06-15 19:32 8771175: The Binomial Functio ... -
joj 1146 标准输入+字符串反转
2011-06-15 18:02 11751146: Word Reversal Re ... -
joj 1149Binary Number 二进制移位操作
2011-06-15 09:50 9681149: Binary Numbers R ... -
joj 2484
2011-06-14 13:35 8632484: Chinese Character A ... -
**joj:1017 fire net 递归回溯的使用
2011-06-14 12:35 11221017: Fire Net Res ... -
joj 1014 the matrix 从八个方向遍历访问矩阵
2011-06-10 20:51 12121014: The Matrix Re ... -
joj 1013 Polynomial Multiplication多项式乘法的计算
2011-06-10 19:54 13291013: Polynomial Multiplic ... -
[zz] c 与 c++ 中的内存分配
2011-06-08 21:45 1337C语言跟 ... -
new 与malloc的区别
2011-06-08 21:24 2491学过C++和C语言的一般都会对编程语言中的内存分配有点小困 ... -
joj 2749 大数比较大小与减法
2011-06-08 16:32 1945/* 题目不难,一个大 ... -
**joj 1903 tug of war 使用动态规划
2011-06-07 10:36 15031903: Tug of War R ...
相关推荐
joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考
JOJ(Java Online Judge)是众多在线编程评测系统之一,为参赛者提供了练习和提交ACM题目的平台。该标题暗示了这是一份包含在JOJ平台上完成并通过测试的ACM试题集合。 【描述】:“在JOJ上做的一些ACM试题,都通过...
每一份程序代码都代表了一个独立的解题思路,涵盖了基础到进阶的算法,如排序、搜索、动态规划、图论等。 2. **ACM**:ACM是"Annual Collegiate Computing Competition"的缩写,这里可能指的是与ACM竞赛相关的题目...
【标题】"joj acm 部分习题解答"揭示了这是一份与JOJ(Judge Online Job)和ACM(国际大学生程序设计竞赛)相关的资源,主要是作者对于某些题目的解题思路和代码实现。JOJ是用于在线评测编程竞赛题目的一种平台,而...
2. **题目的多样性**:题目来源于多种赛事和选拔赛,涵盖了广泛的问题类型和技术挑战,有助于提高参赛者的解题能力和算法水平。 3. **在线裁判系统的功能**:提供了问题列表展示、问题筛选、提交状态查询等功能,...
Java 开源项目 Joj 是一个致力于为 Java 源代码提供对象化表示的库,它类似于 JDOM 在处理 XML 文档中的角色。Joj 的设计目标是为开发者提供一种更直观、更方便的方式来操作和解析 Java 代码,使得在处理大量 Java ...
在计算机科学和算法设计领域,硬币兑换问题是一个常被提及的经典问题,它不仅考验程序员的逻辑思维能力,还检验其对动态规划方法的掌握程度。JOJ 1424题目,即硬币兑换问题,要求参与者通过编程实现一种算法,它能够...
"joj_1237"和"joj10"可能分别对应JOJ平台上的两个具体题目编号,1237号问题和编号为10的一组题目。这些标签有助于分类和检索这些源代码,便于查找特定题目或比赛的解决方案。 在压缩包内的文件名列表中,只有一个...
操作系统中的页面置换算法是内存管理的重要组成部分,尤其是在虚拟内存系统中。先进先出(First In ...这些算法旨在改进FIFO的不足,以更有效地利用有限的物理内存资源,减少不必要的页面替换,从而提高系统的性能。
根据给定的信息,本文将详细解释“acm joj 1600”中的两种大数取模运算方法。此问题主要关注如何高效地计算形如 \(a^b \mod m\) 的表达式,这对于处理大数据或进行密码学运算非常重要。 ### 大数取模运算 #### ...
语言:Français Etre au courant quand JoJ est en live,策划人...约翰·奎因·伊斯特·布鲁和克林·德集团的非官方网站 Développéepar Azamir-倾倒fuclamation defonctionnalité,不满意的联系人Azamir#1089。
吉林大学 joj 1000-2645题代码,嘿嘿,大家就不用在花JPOINT买代码了,祝ACMer实现自己的心愿
通过构建一个以计划、质量、文明和安全为核心的管理体系,利用新技术、新材料和新工艺来提升效率和保证工程质量。 2. **质量目标**:遵循IS09002质量管理体系,设立“优良”作为工程质量的标准。这要求项目经理部...
这个题其实现在想起来也不知道是怎么就给ac的。
该mod基于荒木飞吕彦的JoJo的奇妙冒险漫画和动漫系列。 这个mod也受到KnightDemon的1.12 mod 极大启发。 这个mod的目的是要从专营权中尽可能多地增加Minecraft,该mod目前仅包含Stand能力,其他能力(Hamon,...
Este Projeto签证是由estoque进行的,它是由mer mercadorias uma determinada empresa sejam averiguadas和atualizadas ... 2021年1月20日,由JoséCláudiodeAraújoJúnior和Annielly Ferreira de Sousa所设计。
furystudios 普尔维·扎达塔克(Prvi zadatak) ...DroppingOff - radnikhodajućidolazi做pripadajuće科萨雷(izvedeno kroz provjeru tagova kutije)我卡达joj JE dovoljno blizu,fizičkiJE lan
大智慧最新安装包,老的已经过期不能查询个人自选股,所以推荐最新的大智慧给大家安装