| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4306 人关注过本帖
标题:关于长整数的除法,不知道怎么实现。
只看楼主 加入收藏
ergg
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2016-5-20
结帖率:80%
收藏
已结贴  问题点数:20 回复次数:9 
关于长整数的除法,不知道怎么实现。
要求:
设定a=111111111111111111111111111111(30位),b=999999999999999999999999999999(30位)
    c=555555555555555555555555555555(30位)
求(111111111111111111111111111111999999999999999999999999999999)/(555555555555555555555555555555)的值,只要输出整数位就行。

有两点想不通:
1,怎么定义这么长的数字啊?或者怎么把字符串转为能用的数字?
2,这个除法实在不知道怎么算。。
希望得到指点
搜索更多相关主题的帖子: 字符串 
2016-10-26 14:47
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
搜: 小学竖式除法
2016-10-26 14:58
ergg
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2016-5-20
收藏
得分:0 
回复 2楼 rjsp
除法的地方大概能想通,就是不知道这里怎么定义那么长的数字?如果用字符串输入的话又怎么转换成数字啊? 谢谢回复!
2016-10-26 15:09
word123
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:13
帖 子:333
专家分:1622
注 册:2014-4-5
收藏
得分:0 
字符串中的字符和数字是一对一的,'3'-'0'=3
除法就是减法,被除数减除数,每减一次,结果字符数组就加1,直到被除数小于除数。。
2016-10-26 19:08
ergg
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2016-5-20
收藏
得分:0 
回复 4楼 word123
减法的部分我是有思路的,就是有两个地方不太明白:
1.怎么把两个30位的数字合并成一个60位的数字啊。。
2.30位的数字该怎么定义啊,int不可以用这么长的数字啊。。
  如果我定义成 int a[2]={111...111,999...999}; 好像也不可以,也是error。
  特别不明白这么长的数字怎么定义。。。
2016-10-26 19:44
word123
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:13
帖 子:333
专家分:1622
注 册:2014-4-5
收藏
得分:0 
char a[31],b[31],c[61];

两个30位a,b合并,a字符串赋值到c的前面,b接着赋值到后面就行了
2016-10-26 21:37
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
换成减法,减到不够减,结果就可见。
2016-10-27 09:07
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 5楼 ergg
输入输出都用字符串处理,各位运算用int数组。
2016-10-27 09:10
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:20 
a=111111111111111111111111111111(30位) = (10^30-1)/9*1
b=999999999999999999999999999999(30位) = (10^30-1)/9*9
c=555555555555555555555555555555(30位) = (10^30-1)/9*5

(a*10^30 + b)/c
= [ (10^30-1)/9*1*10^30 + (10^30-1)/9*9 ] / [(10^30-1)/9*5]
分子分母同时除以 (10^30-1)/9
= (10^30 + 9) / 5
= 2*(10^30 + 9) / 10
= ( 2000…共28个零…00018) / 10
= 2000…共28个零…0001 余8
也就是 200000000000000000000000000001

假如用程序计算,竖式除法是小学二三年级的知识,不应该不会呀
程序代码:
#include <stdio.h>
#include <string.h>

unsigned __divide_n( char* restrict rem, const char* b, size_t n )
{
    unsigned quo = 0;
    for( ; strncmp(rem,b,n)>=0; ++quo )
    {
        unsigned carry = 0;
        for( size_t i=n; i!=0; --i )
        {
            carry = 10-carry + (rem[i-1]-'0') - (b[i-1]-'0');
            rem[i-1] = carry%10 + '0';
            carry = 1 - carry/10;
        }
    }
    return quo;
}

void divide( const char* a, const char* b )
{
    b += strspn( b, "0\n" );
    if( !*b ) { puts("INF\n"); return; };
    a += strspn( a, "0\n" );
    if( !*a ) { puts("0\n"); return; };

    const size_t alen = strlen( a );
    const size_t blen = strlen( b );
    if( alen<blen || (alen==blen && strcmp(a,b)<0) ) { puts("0\n"); return; };

    char b_[100];
    b_[0] = '0';
    memcpy( b_+1, b, blen );

    char rem[100];
    rem[0] = '0';
    strncpy( rem+1, a, blen );

    unsigned quo = __divide_n( rem, b_, blen+1 );
    if( quo != 0 )
        printf( "%u", quo );

    for( const char* p=a+blen; *p; ++p )
    {
        memmove( rem, rem+1, blen );
        rem[blen] = *p;

        unsigned quo = __divide_n( rem, b_, blen+1 );
        printf( "%u", quo );
    }
    putchar( '\n' );
}

int main( void )
{
    const char* araw = "111111111111111111111111111111";
    const char* braw = "999999999999999999999999999999";
    const char* craw = "555555555555555555555555555555";

    char a[100];
    strcat( strcpy(a,araw), braw );
    divide( a, craw );
}

2016-10-27 14:10
ergg
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2016-5-20
收藏
得分:0 
回复 9楼 rjsp
谢谢!
2016-11-02 13:53
快速回复:关于长整数的除法,不知道怎么实现。
数据加载中...
 
   



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

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