| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 17883 人关注过本帖, 8 人收藏
标题:第四届蓝桥杯本科B组C语言题
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
接着上次的继续聊吧

上次讲到了大数除法,通过试商来求取商的单个位的值。在这个过程中用到了大数的乘法,准确地说是大数与常规数的乘法。

这一做法虽然可行,但效率比较低,原因是乘法本身就是个高成本的运算。

当然,在试商的过程中使用二分法可以减少乘法的运算次数,但由于结果只是10以内的数(PS:我们仍然在讲十进制下的运算),所以二分法在这里的效果并不明显,平均大约只能节省一两次乘法运算。

相比之下,我们用减法来代替乘法,可以提高更多的效率,毕竟减法运算的成本非常低。

具体步骤是将待算部分与除数作比较;如果待算部分比除数大,则将待算部分减去除数;重复执行这一过程,直至待算部分小于除数;这时减法执行的次数即是这一位的商数。

这种方法适用于各种进制的大数运算,但进制越低越有效。如果使用二进制,那最多做一次就够了。如果使用一万进制,那我建议还是用乘法运算吧,因为减法过程不能应用二分法来提高效率。


大数的除法就讲到这里。以上的分析都是针对大整数的,下面聊聊小数该如何处理。

在说小数的处理之前,先得解决它的存储问题。就不废话了,直奔主题。

目前成熟的小数存储方案有两种,一是定点数,二是浮点数。

这里的点指的就是小数点。

所谓定点数,既是小数点位置固定的数。比如一个实际存储位数为N的空间,我们用它的前K位表示整数部分,后面剩下的N-K位表示小数部分。

所谓浮点数,即是小数点位置可以浮动的数。这种表示法与科学计数法一致,只不过这里一般将尾数规范至0到1之间,其指数部分的数值相当于小数点的位置。

定点数的优点在于操作简单,如果忽略小数点的存在,那它就是个整数。

浮点数的优点在于能表达的数值范围更大(与相同精度的定点数相比),但操作略为复杂,因为运算涉及尾数和指数两个部分。

实际中该使用哪种数,需要具体问题具体分析。以这里的第四题求黄金分割数为例,因为我们很容易确定它是一个大于0.5小于1的数,此时用定点数来存储将是简单有效的。

提醒一下,以上的讨论中我一直没提负数的事。对于负数都是通过一个专门的符号位来表达的,这于整数类似,也可以用原码或补码。关于这些有兴趣的朋友可以自己找一下相关资料,这里就不多讲了(一讲开就收不住了)。

下面开始具体讲解我的代码。

在我的代码中,小数是用定点数来表示的。定点数用一个char型数组表示,每个元素表示小数的一个十进制位。

其中第0元素表示小数的整数部分,之后第1元素表示十分位、第2元素表示百分位等等,即小数点在第0元素与第1元素之间。

程序代码:
#include<stdio.h>

//下面的宏定义了小数的精度,其中ACC表示我们想计算的精度,N表示实际数组的大小
//因为我们说的精度是指小数点后的精确位数,实际长度还要加上整数位及舍入位,所以实际数组长度要多2

#define ACC        100
#define N        ACC + 2

//cmp函数:完成两个小数的比较
//a:第一个小数的指针
//b:第二个小数的指针
//n:两个小数的数组长度
//返回值:当a>b时返回一个正数,当a<b时返回一个负数,当a=b时返回0

int cmp(char * a, char * b, int n)
{
    int i;
    for(i = 0; i < n; i++) //从小数的最高位(即整数部分)开始比较
        if(a[i] != b[i]) return a[i] - b[i]; //如果对应位相同则继续向后比较,否则a、b的比较结果等同于这一位的比较结果
    return 0; //如果两个数不同,那一定会在上面的循环中返回。能执行到这里,那两个数一定相同
}

//sub函数:完成两个小数的减运算
//a:被减数
//b:减数
//n:两个小数的数组长度
//运算结束后,a的值将被修改为差,b的值不变

void sub(char * a, char * b, int n)
{
    int f; //借位标志
    for(f = 0; --n >= 0; f = a[n] < 0 ? (a[n] += 10, 1) : 0) //减运算从低位向高位运算,for语句的迭代部分完成借位标志的判断和处理
        a[n] -= b[n] + f;
}

//div函数:完成两个小数的除运算
//a:被除数
//b:除数
//c:商
//n:a、b、c的数组长度
//运算结束后,c的值将为商,b的值不变,a的值可以认为是达到要求精度后的余数

void div(char * a, char * b, char * c, int n)
{
    int i, j;
    for(i = 0; i < n; i++) //计算从高位向低位进行
    {
        for(c[i] = 0; cmp(a, b, n) >= 0; c[i]++) sub(a, b, n); //先将商的对应位清零,然后开始反复用被除数的待算部分减去除数,同时用商的对应位计数
        a[0] = a[0] * 10 + a[1]; //这一句及以下部分是完成余数的进位,形成下一个待算部分
        for(j = 1; j < n - 1; j++) a[j] = a[j + 1];
        a[n - 1] = 0;
    }
}

//golden_number函数:完成黄金分割数的计算
//x:用于存储计算完成后的黄金分割数
//n:x的数组长度
//这里我对原公式进行了一下变换,这将使收敛速度比直接用原公式快一倍
//原迭代公式为 x1 = 1/(1+x0)
//继续迭代一步 x2 = 1/(1+x1)
//代入上一步即 x2 = (x0 + 1)/(x0 + 2)
//将它作为新的迭代公式使用 x1 = (x0 + 1)/(x0 + 2)
//大家可以重复以上步骤在可操作的范围内得到自己更快的公式

void golden_number(char * x, int n)
{
    char * p, * a, * b, * c, * t;
    int i;

    p = (char *)malloc(n * 3); //本意是为a、b、c申请空间,只不过将三次申请合成一次,提高一些效率,也方便之后的释放
    a = p; b = a + n; c = b + n;

    for(i = 0; i < n; c[i++] = 0); //清空c数组,a和b不需要清零这个动作,这是我确定的。各位在自己的程序中如果不能确定,那建议都做明确的“初始化”这个动作。

    do{ //这里完成公式的迭代,a为公式的分子部分,b为公式的分母部分,c将存储a / b的结果
        //一轮计算完成后进入下一轮迭代,这时上一轮的结果c将成为这一轮的a(一会儿加上个1就是了),所以在这里做一下互换
        t = a; a = c; c = t;
        for(i = 0; i < n; b[i] = a[i++]); //公式中分子和分母只差1,所以先做整体复制
        a[0] += 1;  //现在a就是新的分子了
        b[0] += 2;  //现在b也是新的分母了
        div(a, b, c, n); //对公式进行计算
        b[0] -= 2; //由于上一步的除法运算并不改变b的值,所以这里将b减去2后它的值就退回成了上一次公式计算的结果
    }while(cmp(b, c, n)); //当两次迭代计算的结果差值为0时,终止迭代过程

    for(i = 0; i < n; x[i] = c[i++]); //将结果复制到x中返回给调用方
    free(p); //一定记得释放你申请的空间
}

//output函数:以我们可阅读的方式输出存储在x中的小数

void output(char * x, int n)
{
    int i;
    printf("%d.", x[0]);
    for(i = 1; i < n; printf("%d", x[i++]));
}

int main()
{
    char x[N];
    int i;

    golden_number(x, N);
    if(x[N - 1] >= 5) for(i = N - 2; i >= 0 && ++x[i] > 9; x[i--] = 0); //四舍五入
    output(x, N - 1);
    return 0;
}

重剑无锋,大巧不工
2013-05-15 22:48
wsws23
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:105
专家分:107
注 册:2012-3-13
收藏
得分:0 
崇拜啊 果真选错专业了。。呵呵
2013-05-16 20:31
wsws23
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:105
专家分:107
注 册:2012-3-13
收藏
得分:0 
杨大哥 有时间吗 看了你的一个算法 有点不明白 能否请教一下呢。。
2013-05-16 20:32
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:0 
程序代码:
#include <stdio.h>
#include <string.h>
#define N 1002
char a[N], b[N];

void compare(char *a, char *b) {
    int len1, len2, i, t;
    len1 = strlen(a); len2 = strlen(b); t = 0;
    if(a[0] != '-' && b[0] != '-') {
        if(len1 > len2) printf("a>b\n");
        else if(len1 == len2) {
            for(i = 0; i < len1; i++) {
                t++;
                if((a[i] - '0') == (b[i] - '0')) ;
                else if((a[i] - '0') < (b[i] - '0')) {
                    printf("a<b\n");
                    break;
                }
                else {
                    printf("a>b\n");
                    break;
                }
                if(t == len1) printf("a==b\n");
            }
        }
        else printf("a<b\n");
    }
    if(a[0] == '-' && b[0] == '-') {
        if(len1 > len2) printf("a<b\n");
        else if(len1 == len2) {
            for(i = 1; i < len1; i++) {
                t++;
                if((a[i] - '0') == (b[i] - '0')) ;
                else if((a[i] - '0') > (b[i] - '0')) {
                    printf("a<b\n");
                    break;
                }
                else if((a[i] - '0') < (b[i] - '0')){
                    printf("a>b\n");
                    break;
                }
                if(t == len1 - 1) printf("a==b\n");
            }
        }
        else printf("a>b\n");
    }
    if(a[0] == '-' && b[0] != '-') printf("a<b\n");
    if(b[0] == '-' && a[0] != '-') printf("a>b\n");
}

int main() {
    while(scanf("%s%s", a, b) != EOF)  compare(a, b);
    return 0;
}
顺着B版给的提示把大数比较写出来了!

仰望星空...........不忘初心!
2013-05-17 14:33
燕归来123
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2012-6-23
收藏
得分:0 
看一下,估计不会简单。。。。
2013-05-17 15:12
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
以下是引用wsws23在2013-5-16 20:32:54的发言:

杨大哥 有时间吗 看了你的一个算法 有点不明白 能否请教一下呢。。

哪个算法?但说无妨。

重剑无锋,大巧不工
2013-05-17 22:06
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 64楼 Susake
呵呵,写的有点复杂了,不过逻辑上没什么问题。

你的比较针对的是正常的书写方式,没考虑正号及+0和-0。如果确实没有这方面的需要,那就没有问题。

但一个强烈的建议:函数的功能尽量往简单了写,不要做额外的事情。比如你这个函数叫compare,那最好只完成“比较”的工作,打印输出这类东西不要放在它里面。

当你的工程做大了之后这种耦合度过高的函数可能会给你带来灾难性的后果。

重剑无锋,大巧不工
2013-05-17 22:32
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:0 
呵呵...是呀,以后会注意的..

仰望星空...........不忘初心!
2013-05-17 22:39
wsws23
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:105
专家分:107
注 册:2012-3-13
收藏
得分:0 
回复 67楼 beyondyf
就是在西安电子科技大学OJ上的 Problem 1005 - 跳舞毯 中的  算法里面 几个数组里存放的数据的具体含义 以及 那些变量的
含义 为什么初始化成

    for(p1[0] = i = 0; i < s1n; i++) p1[i + 1] = p1[i] + b; 什么的
有点看不明白  能分析下吗



[ 本帖最后由 wsws23 于 2013-5-18 11:30 编辑 ]
2013-05-18 11:26
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:0 
kk...


[ 本帖最后由 Susake 于 2013-5-19 15:07 编辑 ]

仰望星空...........不忘初心!
2013-05-18 11:35
快速回复:第四届蓝桥杯本科B组C语言题
数据加载中...
 
   



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

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