| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2420 人关注过本帖
标题:连续奇数乘积的二进制位
只看楼主 加入收藏
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
 问题点数:0 回复次数:12 
连续奇数乘积的二进制位
最经碰到这样一个题,我用的方法做了下,可惜算的太慢了,还请各位帮忙,谢谢了,o(∩_∩)o...
给定一连续奇数数列,它们的积有几个二进制位?
Input
第一行为一个数n,表示数列的个数。下面每行两个奇数a,b(1<=a<=b<=10,000,000),分别为数列的首项和末项。
Output
对每个数列,输出一行,该行只有一个整数,表示积的二进制位数。
Sample Input
2
1 3
11 13
Sample Output
2
8
这是我写的程序
#include<stdio.h>
#include<math.h>
#define LOG log(2)
int main(){
    int n;
    int start,end;
    int i,result;
    int mul;
    int preMul;
    while(scanf("%d",&n)!=-1){
          for(i=0;i<n;i++){
              scanf("%d%d",&start,&end);
              result=1;
              mul=1;
              preMul=1;
              while(start<=end){
                  preMul=mul;
                  mul*=start;
                  if(mul/start!=preMul){
                     result+=int(log(float(preMul))/LOG);
                     preMul=1;
                     mul=1;
                     start-=2;
                  }
                  start+=2;
              }
              result+=int(log(float(mul))/LOG);
              printf("%d\n",result);
          }
    }
    return 0;
}
搜索更多相关主题的帖子: 二进制 乘积 奇数 
2008-08-21 17:00
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
顶你一下
希望别人讨论自己的问题,首先就应该顶别人的话题,看了你的题目,我刚刚自己也写了一个,
不才,大家多多讨论,互助:
#include<iostream.h>
#include"LinkedStack.h"

////////////////////////////////////////////////
//main()函数  
////////////////////////////////////////////////
int main()
{
    /*数据的输入*/
    int n;            //奇数列项数的个数
    int start;        //奇数列的开头
    
         do                //如果输入不合格就重输
    {
        cout<<"请输入项数:";
        cin>>n;
        cout<<"输入第一项:";
        cin>>start;
    }while(n<=0 || start%2!=1 );

         /*显示并计算乘积*/
         int result=1;
    for(int i=1;i<=n;i++)
    {
        cout<<start<<" ";
        result=result*start;
        start=start+2;
    };

    /*统计结果的二进制位数*/
    int count=0;          //位数的计数器
    LinkedStack<int> LS;  //链式堆栈
    while(result!=0)
    {
        LS.Push(result%2);//每次把余数压栈
        result=result/2;  //每次整除2
        count++;
    };
    cout<<"一共有"<<count<<"位"<<endl;
         cout<<"二进制形式是:";
    int temp;
    while(!LS.IsEmpty())  //显示堆栈里二进制
    {
                  LS.Pop(temp);
        cout<<temp;
    };

    return 0;
};
//////////////////////////////////main()函数结束
2008-08-22 20:29
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
谢谢你的支持!
可是要是数列很长,光是乘积的话可能就溢出了。
比如输入1 10000000
我的计算出来是106610241位二进制数(33位就超int了),目测用了有1s
但是不知道对不对。可能误差累积错了也说不定。
有没有能解决乘积溢出而且很快的算法呢?
再次谢谢你的支持。o(∩_∩)o...
2008-08-23 00:38
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
说说我的看法吧,既然你编写程序采用的是标准c提供的内部数据类型,
那就意味着本身就是有一定的精度和范围的,例如标准c++的双精度就占
8个字节64位的字长,如果你需要的精度或者范围超出了它所能表示的,
那只能溢出了,如果解决这一问题,建议选择自定义抽象数据类型,举个
简单的例子吧,实现很大范围的整数运算,你可以定义以下这样一个类,
我大概写了一些,供你参考:

#ifndef ARITHMETIC_H
#define ARITHMETIC_H

#include<iostream.h>
#include<cmath>
#include"LinkedStack.h"

////////////////////////////////////////////////////////
//Decimal类的声明和定义
////////////////////////////////////////////////////////
class Decimal
{
private:
    int* A;                //存放每位数的数组
    int  L;                //数的位数
    int currentL;          //当前数的位数
public:
    Decimal(int l=100)     //空构造函数
    {L=l;A=new int[L];currentL=0;setZero();};
    Decimal(char* s,int L);//带参数的构造函数
    ~Decimal()             //析构函数
    {delete [] A;};
    void setZero()         //置零函数
    {for(int i=0;i<L;i++)A[i]=0;};
    //友元重载输出运算符
    friend ostream& operator<<(ostream& os,Decimal& R);
    //友元重载输入运算符
    friend istream& operator>>(istream& is,Decimal& R);
    //友元重载+运算符
    friend Decimal operator+(Decimal& A,Decimal& B);
};
///////////////////////////////////////Decimal类声明结束

////////////////////////////////////////////////////////
//带参数的构造函数
////////////////////////////////////////////////////////
Decimal::Decimal(char* s,int l)
{
    L=l;
    //开辟内存
    A=new int[L];
    //所有位置零
    setZero();
    //把s里的数字内容放入堆栈
    int i=0;
    LinkedStack<char> LS;
    while(s[i]!='#')
    {
        LS.Push(s[i]);
        i++;
    }
    //在把堆栈里的内容放入数组A
    char temp;i=0;
    while(!LS.IsEmpty())
    {
        LS.Pop(temp);
        A[i]=int(temp)-48;
        i++;
          };
    //置当前长度
    currentL=i;
};
////////////////////////////////////////////构造函数结束

////////////////////////////////////////////////////////
//友元重载输出运算符
////////////////////////////////////////////////////////
ostream& operator<<(ostream& os,Decimal& R)
{
    //显示该数
    for(int i=R.currentL-1;i>=0;i--)    
        os<<R.A[i];
    return os;
};
//////////////////////////////////////////////<<重载结束

////////////////////////////////////////////////////////
//友元重载输入运算符
////////////////////////////////////////////////////////
istream& operator>>(istream& is,Decimal& R)
{
    char* s=new char[R.L];
    is>>s;
    //把s里的数字内容放入堆栈
    
    int i=0;
    LinkedStack<char> LS;
    while(s[i]!='#')
    {
        LS.Push(s[i]);
        i++;
    };
    
    //在把堆栈里的内容放入数组A
    char temp;i=0;
    while(!LS.IsEmpty())
    {
        LS.Pop(temp);
        R.A[i]=int(temp)-48;
        i++;
    };
    //置当前长度
    R.currentL=i;
    return is;
};
//////////////////////////////////////////////>>重载结束

#endif
2008-08-23 18:44
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
如果你需要无限或者指定精度或范围的计算,我觉得按位计算是你可以去考虑
的方法,以上的抽象数据类型Decimal我只大概写了构造函数,重载输入输出运算符,你可以试着去重载+,-,*,/运算符,这样你可以在main()函数中当基本类型使用...

其实你所提出的问题比问题的本身要复杂,譬如,我给你个题目,
通过键盘输入n,请计算圆周率的小数点后n位,
并告诉你计算圆周率的莱布尼茨公式是:
∏/4=1-1/3+1/5-1/7+1/9-1/11+1/13-1/15+1/17-1/19+1/21-……
假设输入的n是10000000该怎么编写这个程序呢...
可以去看看数值分析...

在下不才,谨供参考...
2008-08-23 18:53
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
可是题目将来的测试数据就一定会有这种极限的测试
(下面每行两个奇数a,b(1<=a<=b<=10,000,000),分别为数列的首项和末项),
确实可以通过大数类解决范围问题。
那时间上怎么办,一般都要在1s左右啊!我的意思是说这题应该有快速的解法。
这种东西就是考范围和精度 。一般的二进制转化差不多大家都会。其实它只要位数,并不要具体的二进制数,要是那样的话,无论如何都快不了的。光输出上亿位的二进制数就要很久了。
看了你好多贴。阁下的数据结构功底我很佩服。我才入门。
不知你主要看那本书,看你的编程风格像是殷版的。
还有你的大数类我得粘回去慢慢看看,谢谢你的程序。

[[it] 本帖最后由 ivapple 于 2008-8-23 19:59 编辑 [/it]]
2008-08-23 19:55
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
说实话,如果能找到更快的办法,可能就是数学问题了,在下不才,
不过有个问题是值得注意的,有时候代码复杂,并不意味着实质计算过程
就复杂,有的时候,不经意间就调用了一个数学函数,譬如exp()函数,虽然
代码短,但调用这个标准函数实质已经经过了一个泰勒级数的逼近过程了...
也许有些计算本身就是复杂的...

另外,我现在也在构思编写一个类似“super pi”的程序,也就是可以计算
任意精度的圆周率的问题,大家共勉.

我数据结构主看的是严版和殷版的,但是喜欢用面向对象来实现抽象数据类型,喜欢把算法封装起来,也是初级水平啦,大家共勉...
2008-08-23 20:30
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
猜对了,呵呵!
共勉共勉。
2008-08-23 20:51
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
这个问题我解决了。
用阶乘来转换连续奇数乘积。
比如
1*3*5*7=7!/(2*3!)
然后用斯特林公式近似求阶乘
当然是求取对数的,否则溢出。可在常数时间内完成。
程序如下:
#include<stdio.h>
#include<math.h>
const double LOG=log(2);const double PRE=sqrt(2*3.1415926535);double logfac(int n){double i=1.0;  if (n<=9){if(n==0)
             i=0;else{while(n>0)i=i*n--;i=log(i);}}else i=log(sqrt(n)*PRE)+n*log(n)-n;return i;}
int main(){int n,i;int start,end;int result;while(scanf("%d",&n)!=-1){for(i=0;i<n;i++){scanf("%d%d",&start,&end);if(start==end)result=int(log(start)/LOG)+1;
              else{if(start>=3)result=int((log(start)+logfac(end)-logfac(start)-logfac(end/2)+logfac(start/2))/LOG-end/2+start/2)+1;if(start==1)
                     result=int((log(start)+logfac(end)-logfac(end/2))/LOG-end/2)+1;if(end==1)result=1;}printf("%d\n",result);}}return 0;}
程序有点乱,但可以运行(DEV C++ 4.9.9.2和VC 6.0通过)。
a=1
b=10000000
都能算
共有109054009位二进制位,不信的话,自己去验证,o(∩_∩)o...

[[it] 本帖最后由 ivapple 于 2008-9-15 15:39 编辑 [/it]]
2008-09-15 14:57
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
曾经看过求N!的位数,当时就是使用LOG做的。
我想这里用这个一样的可以啦。其实很简单。

倚天照海花无数,流水高山心自知。
2008-09-15 16:28
快速回复:连续奇数乘积的二进制位
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.036299 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved