文章 44
浏览 11238
Double类型数据造成的数据精度丢失

Double类型数据造成的数据精度丢失

这是由一道简单的蓝桥杯例题所得出的小经验,这道题目的主要内容是取一个数小数点后的某几位数字。 首先我想到,要取小数点后的n位数字,只要我将数小数点后的数字其乘以10的n次方,得到的整数部分不就是所求的数字吗? 于是我使用了这样的方式在 C++ 中计算: long long a = long long ( a * pow ( 10 , n ) ); 但最后验证结果却显示我的结果不正确,我与一份正确的代码进行对比,发现除了求阶乘部分不一样外,我们的代码是完全一样的。那么完全正确的代码中是如何求阶乘的呢? #define ll long long ll Qpow( ll a, ll b ) # a为底数 ,b为指数 { ll res = 1; while ( b ) # b不为0 { if ( b & 1 ) res = res * a; #b为1的情况下为最后一次运算,用res保存结果 a = a * a; #求a的平方 b >>= 1; #b除2,当b为1时除2结果为0,下一次跳出循环 } return res; } 那么为什么会出现,两种不同的求阶乘方式,最后的....

数据结构:线性表(番外)

数据结构:线性表(番外)

静态链表: 有时可以借助一维数组来表示线性链表 //------线性表的静态单链表存储结构------- #define MAXSIZE 1000 typedef struct { ElemType data; int cur; }component,Slinklist[MAXSIZE] 数组的一个分量表示一个结点,同时用游标(cur)代替指针指示结点在数组中的位置。在线性表的删除和插入操作时不需要移动元素,仅需要修改游标。 多项式计算: 简单的我们可以想到,用一维数组表示一个多项式,用数组的下标表示多项式中每一项的指数,用数组中每个位置上的值表示对应的系数。 但是这样存在一个问题:形如S(x) = 1 + 3x10000 – 2x20000这样的多项式,指数项的值非常大,但非零项却非常少,导致一维数组浪费的空间很大。 为此我们可以用单链表来实现。在单链表中每个结点有两个数据项(系数项和指数项)。 typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType; //多项式相加 void Add....

数据结构:线性表(2)

数据结构:线性表(2)

顺序存储: 以元素在计算机内的“物理位置”相邻来表示线性表中的数据元素的逻辑关系。 并以表中第一个元素的存储位置作为线性表的基地址。 LOC(ai ) = LOC(ai-1 ) + C LOC(ai ) = LOC(a1 ) + (i-1)×C 线性表顺序存储结构的特点 1.逻辑上相邻的元素,其物理位置也相邻; 2.可随机存取表中任一元素; 3.必须按最大可能长度预分存储空间,存储空间利用率低,表的容量难以扩充,是一种静态存储结构; 4.插入删除时,需移动大量元素,平均移动元素为n/2。 操作: 插入: Status listinsert (List &L,int i,ElenType e) { if (i<1||i>L.lenght) return error; if (L.lenght>=L.maxsize) { newbase=(ElemType*)realloc(sizeof(maxsize+newsize)*sizeof(ElemType)); if (!newbase) exit(1); L.elem=newbase; L.maxsixe+=n....

数据结构:线性表(1)

数据结构:线性表(1)

线性结构特点: 1.存在唯一的第一个“数据元素”。 2.存在唯一的最后一个“数据元素”。 3.除第一个元素外,集合中元素存在唯一后继,除最后一个元素外,集合中元素存在唯一前驱。 线性表: 1.一个线性表是n个数据结构的有序集合 2.线性表中数据元素的个数称为线性表的个数,n=0时称为空表 线性表基本操作: 结构初始化 InitList(*L) 操作结果:构造一个空的线性表 L 销毁结构 DestroyList(*L) 初始条件:线性表 L 已存在 操作结果:销毁线性表 L PriorElem( L, cur_e, *pre_e ) 初始条件:线性表 L 已存在 操作结果:若 cur_e 是 L 中的数据元素,则用 pre_e 返回它的前驱,否则操作失败,pre_e 无定义 NextElem( L, cur_e, *next_e ) 初始条件:线性表 L 已存在 操作结果:若 cur_e 是 L 中的数据元素,则用 next_e 返回它的后继,否则操作失败,next_e 无定义 ListEmpty( L ) 初始条件:线性表L已存在 操作结果:若 L 为空表,则返回 TRUE,否则返回 ....

数据结构:基础部分

数据结构:基础部分

算法: 算法是规则的有限集合,是为了解决特定问题的方法 特性: 1.有穷性、2.确定性、3.可行性、4.零或多个输入、5.一或多个输出 设计要求: 1.正确、2.可读、3.健硕、4.效率与空间 算法效率的度量: 算法中基本操作重复执行的次数记作:T(n)=O(f(n)),称为时间复杂度 一般来说他是最深层循环语句的执行次数的近似。 例如: for (i=2;i<=n;i++) { for (j=2;j<=i-1;i++) { x++; } } x++;这条语句的频度表达式为(n-1)(n-2)/2,所以该代码块的时间复杂度为O(n*n) 例外: 有些问题中,基本语句的重复执行次数还与问题的输入有关,这种情况下,一种方法是计算时间复杂度的平均值,另一种更常用的方法是讨论算法在最坏情况下的时间复杂度。

报数游戏

报数游戏

线性表实验

两种优先搜索

两种优先搜索

深度优先搜索 深度优先搜索采用的是,从首节点出发,一直朝一个方向进行访问相邻节点,直到该方向无相邻节点可以访问为止,这时回到上一节点,从上一节点换一个继续访问,依次重复。直到访问到想要找到的节点,或所有节点全部访问完成。 深度优先搜索的算法模型为: void dfs(int step){ 判断边界 尝试每一种可能 for(i=1;i<n;i++){ 继续下一步dfs(step+i); } 回溯 } 可以看到深度优先搜索,利用的是递归的思想,每次都向深一层访问,直到无法访问。需要注意的是边界条件的判断和尝试吗,每一种可能之后的回溯。 广度优先搜索 广度优先搜索与深度不同,不是采用递归的思路,而是利用了数据结构中的“队列”结构。访问队头元素,将其相邻节点进队,全部相邻元素进栈完成,队头出队。依次重复,直到找到目标节点,或者全部节点被访问完成(也即队列为空)。 深度优先搜索的算法模型为: void dfs(){ while (head<tail){ 判断边界 尝试每一种可能 for(i=1;i<n;i++){ 入队 } 出队队头 } } 以迷宫问题为例 深度优先 vo....

多项式求和

多项式求和

因为参加了CCF的认证考试,加之这假期事情比较少,所以决定静下心来学习几个算法,按照CSP网站上的题目去做,第二道题便是多项式求和。以前在数据结构课上,便了解过多项式求和利用的是栈这个数据结构。不过一直以来遇到需要自己实现的数据结构,我便有点犯怵。不过这次既然决定学习了,所以便决定解决这个问题。 要求如下: ‘+’、‘-’、‘x’、‘/’ 分别表示加减乘除四个基本操作 ‘(’、‘)’分别表示左右括号 要求计算最后结果 思路 分别需要两个栈来分别存放,操作数和操作码。 将多项式作为字符串进行输入。 之后遍历字符串,遇到操作数直接进栈,遇到操作码则较为复杂。 遇到操作码,需要和栈顶存放的操作码进行比较,若高于栈顶操作码,说明之后的出栈的顺序不会影响操作码的计算结果,操作码直接进栈即可。(因为出栈时是后入栈的先出栈,也先计算) 若低于栈顶操作码,则需要将栈顶操作码出栈,操作数出栈两次将结果进行计算,之后再将结果入栈。 若遍历结束,也即遇到'\0'符号,若这是操作码栈中不为空,则需依次出栈计算结果。直到操作码栈为空。 C/C++代码: #include <iostream>....