- 浏览: 143034 次
- 性别:
- 来自: 帝都
文章分类
最新评论
-
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 885/* 算法要求:打印从root到叶节点的路径上的权值和 为 ... -
不带括号的四则运算
2011-10-09 21:24 1416/* 不带括号的表达式的四则运算 使用两个堆栈,一个o ... -
[zz]catalan数的分析与应用
2011-06-25 22:09 1196性质 令h(0)=1,h( ... -
joj 1085: I Think I Need a Houseboat 半圆形侵蚀
2011-06-24 20:54 9361085: I Think I Need a Ho ... -
joj 1032 deck 重心的计算
2011-06-24 19:12 10931032: Deck Result TIME ... -
joj 1186 Box of Bricks 水题
2011-06-19 09:46 9241186: Box of Bricks Re ... -
joj 1062 Computer Versus Mankind 非递归最大公约数 最小公倍数
2011-06-18 15:15 12121062: Computer Versus Mankin ... -
基本的排序:非递归的堆排序
2011-06-17 15:38 0void restore(int root,int le ... -
joj 1817: Triangle 三角形的判定
2011-06-15 20:34 12751817: Triangle Result ... -
×joj 1175 The Binomial Function 递归,递归优化,非递归
2011-06-15 19:32 8351175: The Binomial Functio ... -
joj 1146 标准输入+字符串反转
2011-06-15 18:02 11271146: Word Reversal Re ... -
joj 1149Binary Number 二进制移位操作
2011-06-15 09:50 9211149: Binary Numbers R ... -
joj 2484
2011-06-14 13:35 8082484: Chinese Character A ... -
**joj:1017 fire net 递归回溯的使用
2011-06-14 12:35 10561017: Fire Net Res ... -
joj 1014 the matrix 从八个方向遍历访问矩阵
2011-06-10 20:51 11671014: The Matrix Re ... -
joj 1013 Polynomial Multiplication多项式乘法的计算
2011-06-10 19:54 12891013: Polynomial Multiplic ... -
[zz] c 与 c++ 中的内存分配
2011-06-08 21:45 1297C语言跟 ... -
new 与malloc的区别
2011-06-08 21:24 2407学过C++和C语言的一般都会对编程语言中的内存分配有点小困 ... -
joj 2749 大数比较大小与减法
2011-06-08 16:32 1896/* 题目不难,一个大 ... -
**joj 1903 tug of war 使用动态规划
2011-06-07 10:36 14561903: Tug of War R ...
相关推荐
一、最短路径的概念及应用 在介绍最短路径之前我们首先要明白两个概念:什么是源点,什么是终点?在一条路径中,起始的第 一个节点叫做源点;终点:在一条路径中,最后一个的节点叫做终点;注意!源点和终点都只是相对 于一条路径而言,每一条路径都会有相同或者不相同的源点和终点。 而最短路径这个词不用过多解释,就是其字面意思: 在图中,对于非带权无向图而言, 从源点到终点 边最少的路径(也就是 BFS 广度优先的方法); 而对于带权图而言, 从源点到终点权值之和最少的 路径叫最短路径; 最短路径应用:道路规划; 我们最关心的就是如何用代码去实现寻找最短路径, 通过实现最短路径有两种算法:Dijkstra 迪杰斯 特拉算法和 Floyd 弗洛伊德算法, 接下来我会详细讲解 Dijkstra 迪杰斯特拉算法;
基于faster-rcnn实现的行人检测算法python源码+项目说明+详细注释.zip 使用方法: 1.编译安装faster-rcnn的python接口,代码在:https://github.com/rbgirshick/py 2.下载训练好的caffe模型,百度云链接为:https://pan.baidu.com/s/1w479QUUAwLBS2AJbc-eXIA,将下载的模型文件放到faster-rcnn文件夹的data/faster_rcnn_models文件夹中 3.将本项目中的文件夹替换安装好的faster-rcnn源码中的文件夹 4.使用tools文件夹下的测试脚本运行demo:python person_detect.py
jsp基于Web的可维护的数据库浏览器(源代码+论文+答辩PPT)
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
unet + pytorch 数据科学碗2018-python源码.zip
数据预览链接:https://pan.baidu.com/s/17y5tiSmC5U4d1Mben250gg 提取码:u1da 更多介绍:https://blog.csdn.net/m0_71334485/article/details/138400336
基于Torch Hub的渐进式GAN架构-python源码.zip
JSP基于Iptables图形管理工具的设计与实现(源代码+论文)
使用Keras+TensorFlow+FCN分割KITTI数据集-python源码.zip
基于RRT采样对六轴机械臂进行路径规划Matlab完整源码+代码注释+项目说明.zip
深蹲姿势分析-python源码.zip
基于python实现的交通网络中的流量调控使用复杂网络中的级联失效模型.rar
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
深度残差网络ResNet-python源码.zip
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板
2007-2022商业银行绿色信贷数据绿色信贷余额贷款总额绿色信贷比率不良贷款率 在一定的客观缺失。 1、数据来源:公司年报、可持续发展报告、社会责任报告 2、数 据范围: 36家上市银行 北京银行、常熟银行、成都银行、工商银行、光大银行、贵阳 银行、杭州银行、华夏银行、建设银行、江苏银行、江阴银行、交通银行、民生银行、南京 银行、宁波银行、农业银行、平安银行、浦发银行、青岛银行、青农商行、上海银行、苏农 银行、苏州银行、无锡农村商业银行、西安银行、兴业银行、邮储银行、渝农商行、张家港 行、长沙银行、招商银行、浙商银行、郑州银行、中国银行、中信银行、紫金银行
本文档是课题研究的研究报告内含调研以及源码设计以及结果分析
全球夜间灯光数据 参考文献 [1]徐康宁, 陈丰龙, and 刘修岩. "中国经 济增长的真实性:基于全球夜间灯光数据的检验." 经济研究 (2015). [2] 王贤彬等. "中国地区经济差距动态趋势重估——基于卫星灯光数据的考察." 经济学 (季刊) 16.2(2017):20. 基于美国国家海洋与大气管理局(NOAA) 的DMSP/OLS影像数据和VIIRS/DNB影像数据开发而成的,目前主要反映中 国各省、地级市及县区夜间灯光数据和一带一路沿线国家的夜间灯光数据情况。DMSP/ OLS影像灯光数据目前已经应用于经济类研究,并且已有较多文献发表在诸多高水平杂志 上,因此逐渐受到学者关注。VIIRS/DNB影像灯光数据在国内文献中还未被广泛应 用,但基于其具有许多优点因此逐渐受到学者关注。由于学者通常只能获得NOAA上面的 原始图片资料,将这些图像资料转化为可用数据需要用到较为复杂的计算机和编程技术。 数据包含 核心指标:[DN均值]-计算所得的DN总值/栅格数 项目 字段内容 数 据起始时间 DMSP中国各省份灯光数据(校正后) 省份名称、年度、DN均值 1992~20
Dijkstra算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。以下是Java语言实现Dijkstra算法的一个简单示例,这个示例假设你有一个图的邻接矩阵表示,并且所有边的权重都是正数。 代码定义了一个DijkstraExample类,其中包含了Dijkstra算法的实现。dijkstra方法接受一个图的邻接矩阵和源顶点作为输入,计算从源顶点到图中所有其他顶点的最短路径。minDistance方法用于找到未被考虑的顶点中距离最小的顶点。printSolution方法用于打印最终的最短路径结果。 在main方法中,我们创建了一个图的邻接矩阵,并调用dijkstra方法来计算从顶点0到其他所有顶点的最短路径。 请注意,这个示例仅适用于没有负权边的图,因为Dijkstra算法不能处理负权边。如果你的图有负权边,你可能需要使用Bellman-Ford算法。