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

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

UVA10219-Find the ways  

2009-05-11 20:55:19|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Find the ways !

The Problem

An American, a Frenchman and an Englishwoman had been to Dhaka, the capital of Bangladesh. They went sight-seeing in a taxi. The three tourists were talking about the sites in the city. The American was very proud of tall buildings in New York. He boasted to his friends, "Do you know that the Empire State Building was built in three months?"

"Really?" replied the Frenchman. "The Eiffel Tower in Paris was built in only one month! (However, The truth is, the construction of the Tower began in January 1887. Forty Engineers and designers under Eiffel's direction worked for two years. The tower was completed in March 1889.)

"How interesting!" said the Englishwoman. "Buckingham Palace in London was built in only two weeks!!"

At that moment the taxi passed a big slum ( However, in Bangladesh we call it "Bostii"). "What was that? When it was built ?" The Englishwomen asked the driver who was a Bangladeshi.

"I don't know!" , answered the driver. "It wasn't there yesterday!"

However in Bangladesh, illegal establishment of slums is a big time problem. Government is trying to destroy these slums and remove the peoples living there to a far place, formally in a planned village outside the city. But they can't find any ways, how to destroy all these slums!

Now, can you imagine yourself as a slum destroyer? In how many ways you can destroy k slums out of n slums ! Suppose there are 10 slums and you are given the permission of destroying 5 slums, surly you can do it in 252 ways, which is only a 3 digit number, Your task is to find out the digits in ways you can destroy the slums !

 
The Input

The input file will contain one or more test cases.

Each test case consists of one line containing two integers n (n>=1) and k (1<=<k=<n).
The Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2^31-1.
Sample Input

20 5
100 10
200 15

Sample Output

5
14
23

--------------------------------------------------------------------------------------------------------------------

Ahmed Shamsul Arefin

 

题目大意:给定n和k,求C[n] [k] 这个组合数有多少位。

主要思想:

1.运用公式C[n] [k]=C[n-1] [k-1]+C[n-1] [k] 可以用杨辉三角结合大数方法求出一定范围内的所有组合数,并在计算过程中存储每一个组合数的位数,之后只要O(1)的时间就可以得出答案了。但是这里存在一个问题,虽然题目保证最后的结果在int型范围内,但是n可以很大,只要保证C[n] [k] 的位数在32为就可以了,但是当数组n大于1000时单单算组合数时间上也吃不消了,而且如果n过分的大,程序中也无法提供那么大的数组进行存储。

2.有没有办法避免算出组合数的结果但可以通过n和k得出位数的方法呢?这里可以用到一个公式来求一个十进制数的位数 digit=floor[log10(number)]+1,这个公式对于这道题是足够了,当做组合数运算的时候,把所有的乘法运算换成加法运算,而所有的除法运算都换成加法运算,比如 C[6] [2]=floor[log10(6)-log10(2)+log10(5)-log10(1)]+1。因为log(a*b)=log(a)+log(b),log(a/b)=log(a)-log(b)。

代码如下:

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    double n,k;
    double i;
    double sum;
    while(cin>>n>>k){
        k=k<(n-k)?k:(n-k);
        sum=0;
        for(i=0;i<k;i++){
            sum+=log10(n-i);
            sum-=log10(k-i);
        }
        sum=floor(sum);
        printf("%.lf\n",sum+1);
    }
    return 0;
}

后记:

1.十进制位数的计算可以推广到其他进制上去。这里稍微证明一下,一个n位的十进制数一定大于等于10^(n-1)且小于10^n,所以可以得出digit=floor[log10(number)]+1。

2.我用上面的第一种方法算的时候还要进行大数的运算,代码很长还没对。而用第二种方法的时候竟能达到完全不一样的效果,值得学习!

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

历史上的今天

评论

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

页脚

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