138.74+15.68-49.57138×99的简便计算算法

来源：蜘蛛抓取(WebSpider) 时间：2018-08-11 10:13 标签： 138×99的简便计算

目前就读于华北科技学院通信工程专业，爱好电子数码，安卓以及计算机

自1986年枣庄学院数学专业毕业以来,一直从事小学初中高中数学的教育教学工作和企业职工培训工作.

　　工作中遇到过需要进行极大数据的存储和运算的场景，当时使用Python解决了这个问题，在Python中，整数没有位数限制，使用起来很方便。但是当程序主体使用C/C++实现时，就比较麻烦。所以考虑实现一个大数类，用于大数的存储和运算，后面生成静态库，需要的时候直接调用。

　　大数一般都是以整数队列的形式存储，取一个较大的进制S，队列中的每一个值，相当于一位。假设数组长度为N（0为低位，n-1为高位），则数组表示的值 value =  A0 + A1*S + A2*S2 + ... + An-1*Sn-1。例如 “0” 在数组中存储形式为 , 1234。以下大数的运算全部基于此方式。

　　两个大数比较的方法是：优先比较位数，位数大者为大，位数小者为小；如果位数相等，则依次从高位向低位比较，当前位大的为大，当前位小的为小；如果每一位都相等，则两者相等。

　　大数的加减乘运算都与十进制运算的手算方法相同，区别在于后者是10进制，而前者是S进制。加法计算时，A和B由低位到高位依次求和，需考虑进位。

  • A、B位数可能不相等，因此需要分两部分进行加和；
  • 两次循环结束，需要考虑进位是否为零；
  • A、B位数可能不相等，因此需要分两部分求差值；
  • 减法运算可能会导致差值的若干个高位是无意义的零值，因此需额外的去零操作；

　　大数乘法的计算过程与此相同：对于A(a0a1a2...an-1) * B(b0b1b2...bm-1)，并假设N≥M（被乘数位数不小于乘数时，效率最高），对于B中的每一位 bi，计算其与A的乘积，并在后面补上 i 个零，将结果累加，即为A与B的乘积。

　　除法运算是四则运算中最复杂的运算， 常用的方法是使用多次减法来模拟除法。最简单的方法是被除数不断减去除数，直到结果为负，减的次数即为商，当然这种方法效率太低。

　　网上提供了一些优化方法，例如，在被除数减除数的过程中，被除数每次减去除数的10N倍，以加速被除数衰减过程。

　　这里采用的方法与上述方法原理相似，以23456除以123为例，在进行竖式计算时：以234除以123，得1，余111，以1115除以123，得9，余8，以86除以123，得0，余86，则23456除以123的结果是190。

　　上述过程是为了将未知位数的两个大数相除，转换为多次位数相近的两个数相除，即被除数最多比除数多1位。算法的核心是上述过程中的 234除以124、1115除以123、86除以123，如何得到商和余数。

　　以下提出一种收敛算法：

　　所以，可以通过取A、B的最高两位或一位来预估A、B相除的结果，且预估值≥实际值，并以预估值更新A，多次迭代，直到A<B。设A0=A，A/B的最终结果为C0，推导过程如下：

　　举例（进制S取10亿）：

　　因为误差问题，算法值比实际值大1或与实际值相等，所以算法的最终结果需要向下微调。

　　以下给出收敛过程以及预估值的计算方法：

　　计划实现一个 LargeInt 类，其含义是一个大整数（无负数和小数），实现的核心功能是：字符串构造、格式化字符串输出、加减乘除四则运算以及逻辑比较运算。

　　以C++模板类vector作为大数存储，下标0表示低位，进制S取（10亿，便于格式化输入输出），大数每一位是一个无符号32位整型，乘法运算时的中间值以无符号64位整型承载。

29 // 四则运算符重载 35 // 比较运算符重载 43 // 字符串格式化输出

　　行9、10定义了格式化输入和格式化输出所需的宏，后面会用到。

　　LargeInt 提供了三种构造方法，分别是无符号整型、字符串以及无参数构造。所谓字符串构造，是以十进制字符串为入参，系统对字符串进行分割，转为整数数组，构造LargeInt。

　　以 ”3“ 为例，字符串构造的方法是，从字符串结尾向开头不断截取长度为9的子串，并转为整数，即 45。

15 // 字符串合法性检查，只允许出现字符 0~9 50 // 去零操作，避免整数队列的高位存在多余的零 55 // 注意，如果队列中全为0，要保留最低位的0

　　说明：为避免字符串开头有无意义的零，定义了 ”arrange“ 函数，用于整理队列，去除多余的零值，字符串构造以及后面的减法、除法都需要调用arrange函数。 

　　对于所有的比较运算，可以提取出一个公共函数 ”compare“，该函数比较两个LargeInt的大小，返回1、0、-1，其他比较函数通过调用该函数判断返回值即可。 

 1 // 比较函数，0 相等，1 大于，-1 小于

　　首先定义两个简单的MAX/MIN宏，后面会用到。

　　按照前面提供的算法，实现代码。考虑加法的进位只会是0或1，所以为了减少除法和求模运算，函数中使用 if 判断替代。

　　注意：代码中要避免出现负值，否则会导致计算结果错误；减法运算的结果需要做去零操作。

　　为保证被乘数位数大于乘数，提高计算效率，如果A的位数小于B的位数，则返回B*A。

　　注意：除法计算由高位向低位进行，即求得的第一个商值是结果的最高位，所以要注意插入位置；

　　　　   算法结果需要向下微调，正常情况下，算法结果与实际结果相等，或比实际结果大1，为保险起见，使用了while循环。

（9）格式化字符串输出

　　为便于测试和打印，需要得到 LargeInt 的字符串表现形式，类似于十进制字符串构造，这里将 LargeInt 转为十进制字符串。

　　为了测试加法的性能，定义了两种测试用例：10位加10位、10位加5位（此处的位长指队列长度，对应十进制的位数是其9倍），每种测试用例有100个，运行1000次，求平均运行时长。对于减法乘法和除法，测试方法与加法相同。

　　在个人电脑上的测试结果如下：

  • 加法和减法效率已经比较高了，算法上基本没法进一步优化；
  • 以加法为参考，10位 乘 5位的时长是加法的2倍，10位 乘 10位的时长是加法的3倍。乘法结果的位数是乘数和被乘数两者位数的乘积，因此随位数增加，乘法消耗的时长和对应的加法消耗的时长的比值会更大；
  • 除法时长增长规律似乎与乘法相反，除法对被除数和除数间的位数差值更敏感，差值越大，耗时越大。

　　在Debug模式下跑gtest测试用例，在Release下跑性能测试.

27 // 字符串合法性检查，只允许出现字符 0~9 62 // 去零操作，避免整数队列的高位存在多余的零 67 // 注意，如果队列中全为0，要保留最低位的0

数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？
Jarvis计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。
目前（截止2011年）发现的最少提示数9×9标准数独为17个提示，截止2011年11月24日16:14，共发现了非等价17提示数谜题49151题，此数量仍在缓慢上升中，如果你先发现了17提示数的题目，可以上传至“17格数独验证”网站，当然你也可以在这里下载这49151题。
Gary McGuire的团队在2009年设计了新的算法，利用Deadly Pattern的思路，花费710万小时CPU时间后，于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明，继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。

以上内容来自于百度百科。

网络上有很多解数独的算法，例如舞蹈链算法、遗传算法等。参考
递归回溯对数独情有独钟。
本文解数独用的是候选数法（人工选择）+万能搜索法，搜索+剪枝（递归+回溯），参考博文：

1）未优化的算法-只有递归回溯（单解或多解）

从第一个位置开始依次检索所有格子（暴力），执行时间会比较长。
多解与单解：很简单，在找到解的语句返回false表示继续递归寻解，返回true表示停止寻解（不会复位，不回溯）

2）优化算法-添加（唯一法或唯余法、摒除法、三链数删减法）

由于前面一种未经过优化搜索条件，属于“暴力型”解法（Brute Force），若碰到需要递归非常大的空间时，消耗时间将是非常长的，还有可能会抛出内存溢出的异常。如果按照人的思维去解数独，绝对不会像计算机一样呆呆的一个一个地去试，相反，人工解数独首先考虑的是将候选数最少（通常为1，必填）的格子先肯定的填上去，各种方法都用尽后，所谓山穷水尽时才会考虑试填，（即计算机的运作方式：递归回溯），而试填时也是从最少的候选数的格子开始（通常为2），这样能有效的找到解，而计算机只能使用暴力。所以，在算法中加上人工智能选择的话，可以大大提高执行效率。
基本解题方法：隐性唯一解（Hidden Single）及显性唯一解（Naked Single），摒除法，余数法，候选数法

要仿照人工求解模式，需要采用候选数法对候选数进行删减法，其中可以应用到唯一（余）法，摒除法（行列宫）等。对应关系：
唯一（余）法：某个格子的候选数只剩下一个数字，则该数字必填如该格子。对应于唯一候选数法
摒除法：如果某个数字在某宫所有格子的所有候选数中总共只出现一次，则该数字必填入候选数包含它的那个格子中。行列情况同理。对应于隐性唯一候选数法。
三链数删减法:找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形，
进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。

  • 反复应用候选数删减法寻找必填项，直到候选数未发生变化（即找不到必填项了）

  • 然后才递归寻解（如果上一步骤找到了解，那递归寻解只输出解了）

//输入格式要求0作为占位符(表示待填)，只接受数字字符串，长度为81位 //初始化数独和候选数 //校验给出的数独题目是否为有效数独（即某行列宫中有重复的数字则无效） //初始化候选数(唯一法或唯余法),数独无解返回false //如果待填格子候选数个数为0，不合格数独（无解数独） //候选数个数为1，对应于唯一法或唯余法，可以100%的将该候选数填入该格子中，并重新计算候选数 //删除(i,j)等位格群上的候选数k，当(i,j)上可以肯定的填入数字k时(等位格局包含除自身外共20个格子) //每次调用此方法后，候选数发生了变化，需要再次检查唯一（余）性质 //只要有一个候选数发生了删减，则返回true //唯一法或唯余法或唯一候选数法，检查每个格子候选数的个数是否为1 //此为最基础的方法、应用其他方法发生了删减候选数时都要应用此方法检查一遍 boolean change = false;//表示是否候选数是否发生变化(当有删除候选数操作时则发生了变化) return change;//若无删减候选数操作，意味着一个必填项都没有找到返回false //摒除法或隐性唯一候选数法,某个数字候选数只在该宫(行列)中的某一个格子出现（按照数字）,即在该宫所有格子所有候选数中总共只出现一次。 boolean change = false;//表示是否候选数是否发生变化(当有删除候选数操作时则发生了变化) //表示该格子只能填入k //表示该格子只能填入k //表示该格子只能填入k //特殊条件：某一个数字在某一个宫中恰好只出现2次或3次，并且出现的位置恰好形成一条线（行或列）， //则可以删除该线上的其它宫格中的这个数字 //恰好只出现一次时，摒除法可以处理 //隐性三链数删减法：在某行，存在三个数字出现在相同的宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数。 //那么这三个宫格的候选数中的其它数字都可以排除。当隐形三链数出现在列，九宫格，处理方法是完全相同的。 //三链数删减法：找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形， //进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。 //需要用3重循环遍历某行所有格子3个结合的情况 //数对删减法,如果某宫中两个格子的候选数个数只有2个且都一样，则可以删除其他格子中的这两个候选数 //需要双层循环两两组合 /*//四链数删减法，尽管此法应用得不多，但在特殊情况下能找到必填项 * 删减某宫（行列）除某些格子(a、b、c)外的其他格子的候选数,或者删除某些格子中的某些候选数 * @param c c的绝对位置，取值0~80或者-1，取-1时，表示数对删减法 * @param type 取值1、2、3，分别表示为 行删除、列删除、宫删除 * @param method 取值1、2，分别表示为三链数（数对）删除法（删其他格子）、隐性三链数删除法（删自身格子） //取abc三个字符串的并集 //从(i,j)候选数中删除指定的候选数keys //万能解题法的“搜索+剪枝”,递归与回溯 //从(i,j)位置开始搜索数独的解,i和j最大值为8 //寻找可填的位置（即空白格子），当前(i,j)可能为非空格，从当前位置当前行开始搜索 outer://此处用于结束下面的双层循环,标记不赞成使用，但在此处很直观 //如果从当前位置并未搜索到一个可填的空白格子，意味着所有格子都已填写完了，所以找到了解 //计算下一个元素坐标，如果当前元素为行尾，则下一个元素为下一行的第一个位置（未填数）， //否则为当前行相对当前元素的下一位置 //递归未找到解，表示当前(i,j)填k不成功，则继续往下执行复位操作，试填下一个数 //反复应用唯一（余）法检查每个格子的候选数的个数是否为1以及应用摒除法找寻必填数字 //直到候选数不在发生变化（即没有候选数删减操作） boolean f1 = single();//唯一（余）法，最基础的方法、应用其他方法发生了删减候选数时都要应用此方法 boolean f2 = exclude();//摒除法，优先级比唯一（余）法低一点点，也是最基础的方法 //再应用一次基础方法，确保万无一失 //数独规则约束，行列宫唯一性,检查(i,j)位置是否可以填k //行列约束,宫约束，对应宫的范围 起始值为(i/3*3,j/3*3),即宫的起始位置行列坐标只能取0,3,6

以下是对一个标准17数独（单解）的执行结果。

从上面示例可以看出，应用候选数删减法（人工）完全把一个标准17数独解出来了，没有用到递归。
即便候选数删减法（人工）只找出了部分的必填项，但也会大大减少了递归执行的时间。

我要回帖

更多关于 138×99的简便计算 的文章

 

随机推荐