注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

程序中的数学  

2009-03-24 16:25:09|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Herd Sums

Acceteped : 37   Submit : 76
Time Limit : 1000 MS   Memory Limit : 65536 KB

Description

The cows in farmer John's herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N.

Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10.

Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.
 

Input

* Line 1: A single integer: N
 

Output

* Line 1: A single integer that is the number of ways consecutive cow brands can sum to N.
 

Sample Input

15
 

Sample Output

4

Source

USACO 2003 March Orange

题目大意:对于给定的一个数n,可以表示成几种连续的自然数相加之和。

主要思想:假设自然数n=m+(m+1)+......+(m+k),化简后m=(2*n-k*k-k)/(2*(k+1)),所以题目转化为,存在几组整数对(k,m)使得上述的等式成立。即对于k=0,1,......,(m<1时结束)能否使等式的右边整除,及对右边等式取余后为0。

注意问题:循环的结束条件,即注意跟m相关的量为多少时应该结束循环。

代码如下:

#include<iostream>
using namespace std;
int main(){
    int n,sum;
    int k,m,temp;
    int a,b;
    while(cin>>n){
        m=1;sum=0;
        for(k=0;m>0;k++){
            a=2*n-k*k-k;
            if(a==0)break;
            b=2*(k+1);
            temp=a%b;
            if(temp==0){
                sum++;
            }
            m=a/b;
        }
        cout<<sum<<endl;
    }
    return 0;
}

后记:一些复杂的问题转换为数学问题可以很大的降低计算的复杂度。

  评论这张
 
阅读(185)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017