计算机视觉技术 JavaSE 整数转换 map遍历 idea 常用快捷键 laravel class datetime pointers 3d Modernizr vue的优点 后台管理ui react视频教程 jquery绑定change事件 teamviewer验证被拒绝 js键值对数组 idea批量替换快捷键 python程序实例 python环境变量配置 python处理json文件 java中的多态 java课程 java接口的使用 java中的集合 java删除目录 战地女记者 java电子书下载 atq 电池救星 主板芯片组天梯图 3dmax插件神器 go2lan JScodeblocks汉化包 苹果x银色 mysql时间比较 大数据之路 华为杂志锁屏怎么设置 HTA 华为手环怎么连接手机
当前位置: 首页 > 学习教程  > 编程语言

蓝桥杯 算法训练 - 连续正整数的和 78这个数可以表示为连续正整数的和,1+2+3,18+19+20+21,25+26+27。   输入一个正整数 n(<=10000)   输出 m 行(n有m

2020/10/8 19:43:51 文章标签:

问题描述 78这个数可以表示为连续正整数的和&#xff0c;123&#xff0c;18192021&#xff0c;252627。   输入一个正整数 n(<10000)   输出 m 行(n有m种表示法)&#xff0c;每行是两个正整数a&#xff0c;b&#xff0c;表示a(a1)…bn。   对于多种表示法&#xff0c…

问题描述

78这个数可以表示为连续正整数的和,1+2+3,18+19+20+21,25+26+27。
  输入一个正整数 n(<=10000)
  输出 m 行(n有m种表示法),每行是两个正整数a,b,表示a+(a+1)+…+b=n。
  对于多种表示法,a小的方案先输出。
例子

样例输入
78
样例输出
1 12
18 21
25 27
数据规模与限制

时间限制:1.0s 内存限制:256.0MB
提示

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。

思路:

只需要用两个循环找出两个数,然后再用一个循环判断这两个数之间的数相加等不等于n就行了。
不过有趣的是,如果不加一些条件,输出结果时就会超时。
在下面会用3段代码举例子。
1)超时代码:

#include <stdio.h>
int main ()
{
	int n;
	scanf("%d",&n);
	
	int i,j,k,sum;
	
	for(i=1;i<n;i++)
	{
		
		for(j=i+1;j<n;j++)
		{
			sum=0;
			for(k=i;k<=j;k++)
			{
				sum+=k;
			}
			if(sum == n)
			{
				printf("%d %d\n",i,j);
				break;
			}
		}
	}
	return 0;
 } 

在这里插入图片描述
可以看到基本都超时了。

2)不超时的AC代码:

#include <stdio.h>
int main ()
{
	int n;
	scanf("%d",&n);
	
	int i,j,k,sum;
	
	for(i=1;i<n;i++)
	{
		
		for(j=i+1;j<n;j++)
		{
			sum=0;
			for(k=i;k<=j;k++)
			{
				sum+=k;
				if(sum>n)//如果发现大于n了,那么后面的一定都大于n,break;
					break;
			}
			if(sum == n)
			{
				printf("%d %d\n",i,j);
				break;
			}
		}
	}
	return 0;
 } 

在这里插入图片描述
发现基本都大于100ms,能不能更快呢?
3)比较高效率的代码

#include <stdio.h>
int main ()
{
	int n;
	scanf("%d",&n);
	
	int i,j,k,sum;
	int flag=0;
	for(i=1;i<n;i++)
	{
		flag=0;
		for(j=i+1;j<n;j++)
		{
			sum=0;
			for(k=i;k<=j;k++)
			{
				sum+=k;
				if(sum>n)
				{
					flag = 1;//如果超过了,那么下一层循环肯定也会超过,做出标记,在下一层循环也直接break;
					break;
				}
			}
			if(flag==1)//如果发现标记了,就break;
				break;
			if(sum == n)
			{
				printf("%d %d\n",i,j);
				break;
			}
		}
	}
	return 0;
 } 

在这里插入图片描述
可以看到基本都在1ms了,一个简单的优化就可以节约约百毫秒,还挺有趣的…


本文链接: http://www.dtmao.cc/news_show_250169.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?