1 战神大吉大利!

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 17w+

分治算法 —— 算法总结

时间总是太快啦!我将近花费四天左右的时间来学习分治算法,基本把大部分分治算法的经典例题做了一遍,但路漫漫其修远兮,吾将上下而求索。接近两天的时间完成分治法相关的博客记录。今天来对分治算法总结一下。虽然分治算法的相关例题做的也不多也不少,但我仍旧不敢说我对分治算法了如指掌,胸有成竹啦!顶多算是入门啦吧!此处附上分治算法的经典例题,来源以及题解。(1)大整数乘法(2)棋盘覆盖(3)合并排序(4)快速排序(5)循环赛日程表分治算法 ; 一般大规模问题化为小规模问题,最后由小规模问题的解合并得到大

2020-07-29 14:54:57

麦森数 —— 高精度乘法 与 快速幂综合应用

麦森数 —— 高精度乘法 与 快速幂综合应用题目描述题目链接题解1,位数解法位数举一反三2,500位数的计算结语题目描述形如2^ P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2^P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。任务:从文件中输入P(1000<P<3100000),计算2^P-1的位数和最后500位数字(用十进制高精度数表示)输

2020-07-28 17:51:34

数论 —— 高精度乘法

高精度乘法高精度乘法其实是大整数之间的相乘,大整数之间的相乘如果超过 int 或 long long 类型是无法用变量来表示的。有的大整数甚至超过500位。那如何 精确的 表示大整数与大整数之间的相乘呢?答案是使用整型数组来表示 个位 百位 千位…举例说明:165 * 13 ,我们可以发现我们先把各个位置的数据先算起来 3 * 165 时为 3 18 151 * 165时为 1 6 5 注意要错位, 再将相应位置的数据加起来为 1 9 23 15

2020-07-28 15:17:12

分治法 —— 取余运算 (快速幂)

取余运算题目描述给你三个整数 b,p,k,求 b^p mod k输入格式输入只有一行三个整数,分别代表 b,p,k输出格式输出一行一个字符串 b^p mod k=s,其中 b, p, k 分别为题目给定的值, s 为运算结果。输入2 10 9输出2^10 mod 9=7说明/提示2^10 = 10242 1024 mod 9=7数据规模与约定对于 100%100% 的数据,保证 0 <= b,p < 2^31, 1 < k < 2 ^31

2020-07-28 12:32:36

分治法 —— 快速幂

快速幂何为快速幂Code 递归 (非快速幂)Code 递归 (快速幂)Code 迭代 (非快速幂)Code 迭代 (非快速幂)结语何为快速幂例如 a ^ b ,按正常情况下我们需要从1 开始迭代到 b ,若b是较小数据,那对程序的影响微乎其微,若b是上千的数据,从1遍历到 b 需要的时间非常大, 大大降低程序的性能!快速幂采用分治的策略,一分为二, 二分为四,四分为八…a ^ b =( (a ^2) ^ (b/ 2) ) * a ^ (b % 2) = (a ^ (b/2))^ 2 * a

2020-07-28 11:38:42

分治法 —— 光荣的梦想 (归并排序应用3)

光荣的梦想【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量,平衡瞬间即被打破。KB决定求助于你,帮助他完成这个梦想。一串数列即表示一个世界的状态。平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列

2020-07-28 10:55:36

分治法 —— 求逆序对个数 (归并排序应用2)

求逆序对个数题目描述有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000),若i<j,并且A[i]>A[j],则称A[i]与A[j]构成了一个逆序对,求数列A中逆序对的个数。例如,5 2 4 6 2 3 2 6,可以组成的逆序对有(5 2),(5 4),(5 2),(5 3),(5 2),(4 2),(4 3),(4 2),(6 2),(6 3),(6 2),(3 2)共:12个输入共两行,第一行有一个正整数n,第二行有n个整数

2020-07-27 21:37:40

分治法 —— 最大子序和 ( 归并排序应用1)

LeetCode 最大子序和题目描述给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。力扣(LeetCode) 最大子序和本题有四种解法,暴力, 动态规划, 分治法 以及 贪心法。每种解法各有千秋,此处主要讲解分治法如何实现最大值产生于红色部分, 绿色部分以及蓝色部分三者之间如何求红色,绿色,蓝色三个part各自

2020-07-27 20:32:00

分治法 —— 归并排序(递归和非递归)

归并排序 ( 递归 与 非递归)合并排序之递归Code 递归合并排序之迭代Code 迭代1(So easy)Code 迭代2(有点绕)结语归并排序又称为合并排序(合久必分,分久必和) 分而治之的策略归并排序不是一下子将整个数组排序,而是不断的分离直到分为一个数,一个数本身就是有序的,最后不断的合分而治之 大规模问题化为小规模问题,小规模问题的解合并即是大规模问题的解合并排序之递归Code 递归#include <cstdio>//归并排序采用递归方式//先分 后比 再和/

2020-07-27 19:46:13

分治法 —— 快速排序(递归,迭代,非递归)

快速排序快速排序三种方法,你值得参考!!!快速排序1,快速排序之递归Code 递归2,快速排序之迭代Code 迭代3,快速排序之非递归Code 非递归4,结语快速排序在所有排序中基本上速度是最快的啦(前提是基准元素要选的好,没选好基准元素很可能变为冒泡排序)快速排序算法思想是分治策略,但可以有多种手段来实现1,快速排序之递归其实快速排序之递归是传统的快速排序。为什么说是传统的呢? 大部分的快速排序无论是在教材上还是在一些博客上基本采用递归分治来实现。因为此方法比较好懂递归快速排序一般都是两个游

2020-07-27 16:06:19

分治法 —— 黑白棋子移动

黑白棋子移动题目描述题意解读Code结语题目描述有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:○○○○○●●●●●移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。如n=5时,成为:○●○●○●○●○●任务:编程打印出移动过程。样例输入 Copy7样例输出 Copystep 0:ooooooo

2020-07-27 13:55:02

分治法 —— 循环比赛日程安排表

循环比赛日常安排表题目描述提示题目解题Code 递推Code 递归结语题目描述设有n个选手进行循环比赛,其中n = 2^m,要求每名选手要与其他n - 1名选手都赛一次,每名选手每天比赛一次,循环赛共进行n - 1天,要求每天没有选手轮空。输入一行,包含一个正整数m。输出表格形式的比赛安排表(n行n列),每个选手的编号占三个字符宽度,右对齐。样例输入 Copy3样例输出 Copy1 2 3 4 5 6 7 82 1 4 3 6 5 8 73 4 1

2020-07-27 11:59:47

分治法 —— 棋盘覆盖

棋盘覆盖题目描述讲解Code说明:题目描述在一个2k x 2k ( 即:2^k x 2^k )个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。输入输入文件第一行为整数k,(棋盘大小是2k*2k 1<=k<=10),第二行是两个整数,代表特殊方格所在行号和列号。输出特殊点用0输出,数据间用制表符隔开(‘t’),

2020-07-27 10:27:58

入门模拟【关于模拟题总结】

模拟题模拟题分为 简单模拟,查找元素, 图形输出, 日期处理, 进制转换 以及 字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的一类题目。此类题目不涉及算法,完全根据题目描述进行代码的编写,主要考察代码能力!!!【注意】虽听起来可能蛮简单的,但绝不是1 + 1 = 2的题目!!!有些题实现起来确实有小难度!说明每个part基本都有我写的博客题解,主每个part的题解都是价值蛮大的题(主要以PAT甲乙级为主,code up 为辅)关于代码这里不提供,网上有太多啦!

2020-07-14 10:42:32

模拟题 —— 字符串拔高题2(PAT 乙级 1024 科学计数法 (20分) )

模拟题介绍入门模拟题 分为简单模拟,查找元素,图形输出,日期处理,进制转换字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的一类题目。此类题目不涉及算法,完全根据题目描述进行代码的编写,主要考察代码能力!!!模拟题 ———— 字符串处理(拔高题)【PAT 乙级 B 1024】 科学计数法 (20分)字符串处理问题很能体现代码能力的一种题型,一般实现逻辑会非常麻烦而且可能会有很多的细节和边界情况,因此对代码能力弱的会有较大难度但这也是进阶大神的必经之路。唯一的方法:多做

2020-07-14 09:07:19

模拟题 —— 字符串拔高题1(PAT 甲级 1082 Read Number in Chinese (25分) )

一 ,模拟题介绍入门模拟题 分为简单模拟,查找元素,图形输出,日期处理,进制转换字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的一类题目。此类题目不涉及算法,完全根据题目描述进行代码的编写,主要考察代码能力!!!模拟题 ———— 字符串处理(拔高题)【PAT 甲级 1082】 Read Number in Chinese (25分)字符串处理问题很能体现代码能力的一种题型,一般实现逻辑会非常麻烦,而且可能会有很多的细节和边界情况,因此对代码能力弱的会有较大难度,但这也是

2020-07-13 21:26:15

多种解法 ——【PAT B1009】 说反话 (20分)

模拟题介绍入门模拟题 分为简单模拟,查找元素,图形输出,日期处理,进制转换字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的一类题目。此类题目不涉及算法,完全根据题目描述进行代码的编写,主要考察代码能力!!!模拟题 ———— 字符串处理【PAT B1009】 说反话 (20分)字符串处理问题很能体现代码能力的一种题型,一般实现逻辑会非常麻烦,而且可能会有很多的细节和边界情况,因此对代码能力弱的会有较大难度,但这也是进阶大神的必经之路。唯一的方法:多做多想,积累经验

2020-07-10 15:41:14

【Code Up 问题 A】:日期差值

模拟题介绍入门模拟题 分为简单模拟,查找元素,图形输出,日期处理,进制转换,字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的一类题目。此类题目不涉及算法,完全根据题目描述进行代码的编写,主要考察代码能力!!!今天讲述一道模拟题 —— 日期处理大家应该知道日期,时间等等的转换处理有些许麻烦的。时间些许好一些,但比如日期需要考虑闰平年,每个月是否是大小月等等…【Code Up 问题 A】:日期差值题目描述有两个日期,求两个日期之间的天数,如果两个日期是连续的我们规定他

2020-07-09 15:18:44

【PAT1065】 A+B and C (64bit) (20分)

模拟题稍微拔高一点的模拟题【PAT1065】 A+B and C (64bit) (20分)看本题之前我们来看一道类似的题目PAT 乙级【PAT 乙级1011】 A+B 和 C (15分)题目类似,唯一不同的地方如下:给定区间 [−2^31​​ ,2^​31] 内的 3 个整数 A、B 和 C,请判断 A+B 是否大于 C。由于int整型范围为 [−2^31​​ ,2^​31 - 1],因为超过int的范围且两个最大值或者两个最小值相加都未超过long long 8字节范围,故使用long l

2020-07-07 16:42:16

【PAT A1046】/ 【Code Up E】 Shorest Distance(20)

标题简单模拟介绍PAT甲乙级中入门模拟题,入门模拟题又分为简单模拟,查找元素图形输出,日期处理,进制转换,字符串处理等等!何为模拟题?模拟题是一类“题目怎么说,你就怎么做的”的题目如果实现不太麻烦可以称之为就“简单模拟”!!!此类题目不涉及算法,完全根据题目描述进行代码的编写主要考察代码能力虽听起来可能蛮简单的,但绝不是1 + 1 = 2的题目!!!有些题实现起来确实有小难度!本次讲述两道稍微拔高的模拟题PAT 甲级 A1046 Shortest Distance (20分)

2020-07-07 15:42:33

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。