《趣题学算法》—第0章0.2节计算问题
本节书摘来自异步社区《趣题学算法》一书中的第0章0.2节计算问题,作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
0.2 计算问题
上面已经说到什么是计算问题,下面就来看一个有趣的计算问题。
问题描述
这个学期Amy开始学习一门重要课程——线性代数。学到行列式的时候,每次遇到对给定的序列计算其逆序数,她都觉得是个很闹心的事。所以,她央求她的好朋友Ray为她写一段程序,用来解决这样的问题。作为回报,她答应在周末舞会上让Ray成为她的伦巴舞舞伴。所谓序列A的逆序数,指的是序列中满足iA[j]的所有二元组的个数。
输入
输入文件包含若干个测试案例。每个案例的第一行仅含一个表示序列中元素个数的整数N(1leqslantNleqslant500000)。第二行含有N个用空格隔开的整数,表示序列中的N个元素。每个元素的值不超过1 000 000 000。N=0是输入数据结束的标志。
输出
每个案例仅输出一行,其中只有一个表示给定序列的逆序数整数。
输入样例
3 1 2 3
输出样例
0
这是本书要讨论,研究的一个典型的计算问题。理解问题是解决问题的最基本的要求,理解计算问题要抓住三个要素:输入、输出和两者的逻辑关系。这三个要素中,输入、输出数据虽然是问题本身明确给定的,如果输入包含若干个案例则要理清每个案例的数据构成。
例如,问题0-1的输入文件inputdata(本书所有计算问题的输入假设均存于文件中,统一记为inputdata)中含有若干个测试案例,每个案例有两行输入数据。第1行中的一个整数N表示案例中给定序列的元素个数。第二行含有表示序列中N个元素的N个整数。当读取到的N=0时意味着输入结束。
所谓输入、输出数据之间的逻辑关系,实质上指的是一个测试案例的输入、输出数据之间的对应关系。为把握这一关系,往往需要认真、仔细地阅读题面,在欣赏题面阐述的故事背景之余,应琢磨、玩味其中所交代的反应事物特征属性的数据意义,以及由事物变化、发展所引发的数据变化规律,由此理顺各数据间的关系,这是设计解决问题的算法的关键所在。
例如,如果我们把问题0-1的一个案例的输入数据组织成一个数组A[1..N],我们就要计算出序列中使得iA[j]成立的所有二元组,统计出这些二元组的数目,作为该案例的输出数据加以输出——作为一行写入输出文件outputdata(本书所有计算问题的输出假设均存于文件中,统一记为outputdata)。
对问题有了正确的理解之后,就需要根据数据间的逻辑关系,找出如何将输入数据对应为正确的输出数据的转换过程。这个过程就是通常所称的“算法”。通俗地说,算法就是计算问题的解决之道。
例如,对问题0-1的一个案例数据A[1..N],为计算出它的逆序数,我们设置一个计数器变量count(初始化为0)。从j=N,A[j]开始,依次计算各元素与其前面的元素(A[1..j−1])构成的逆序个数,累加到count中。当j 2时,结束计算返回count即为所求。
异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区,也是国内领先的IT专业图书社区,致力于优质学习内容的出版和分享,实现了纸书电子书的同步上架,于2015年8月上线运营。公众号【异步图书】,每日赠送异步新书。
相关文章
- Java实现 蓝桥杯 算法提高 计算超阶乘(暴力)
- Java实现 蓝桥杯 算法提高 计算超阶乘(暴力)
- Java实现 蓝桥杯VIP 算法训练 JAM计数法
- Java实现 蓝桥杯 算法训练 天数计算
- Java实现 蓝桥杯 算法提高 矩形靶
- Java实现 蓝桥杯VIP 算法提高 淘淘的名单
- Java实现 蓝桥杯VIP 算法训练 平方计算
- Java实现 蓝桥杯VIP 算法训练 薪水计算
- Java实现 蓝桥杯VIP 算法训练 斜率计算
- Java实现 蓝桥杯VIP 算法训练 最大值与最小值的计算
- Java实现 蓝桥杯VIP 算法训练 最大值与最小值的计算
- Java实现 蓝桥杯 算法提高 概率计算
- Java实现 蓝桥杯 算法提高 日期计算
- Java实现 蓝桥杯 算法提高 概率计算
- 非对称加密算法-DH算法
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.65】CVPR 2023 | 清华团队即插即用型网络架构—Slide-Transformer
- STP中各算法接口开销(COST)计算方式
- 数据挖掘中分类算法小结
- Atitti 摘要算法 散列算法SHA1 和 MD5 crc32 目录 1.1. CRC(Cyclic Redundancy Check,循环冗余校验)算法出现时间较长1 1.1.1. 数据摘要算
- Atitit 算法之道 attilax著 1. 编码算法3 1.1. Base64 htmlencode urlencode3 2. Ui方面的算法3 2.1. 软键盘算法 计算软键盘上下
- CV之HOG:图像特征提取之基于方向梯度直方图HOG算法的简介、代码实现(计算图像相似度)之详细攻略
- CV之FD之HOG:图像检测之基于HOG算法、简介、代码实现(计算图像相似度)之详细攻略
- ML之SSIM:基于输入图片RGB的三维向量利用SSIM(结构相似性度量)算法实现计算图像相似度案例
- CV之FD之HOG:图像检测之基于HOG算法、简介、代码实现(计算图像相似度)之详细攻略
- 多目标遗传优化算法NSGA-Ⅱ算法(Matlab)
- 基于DNN深度学习网络的OFDM信号检测算法的仿真,对比LS和MMSE
- 基于farrow结构的时间同步算法matlab仿真
- 基于萤火虫算法优化的lssvm回归预测-附代码
- 隐马尔可夫模型-概率计算算法
- Java开发 | 数据结构和算法之——递归算法
- NLP算法竞赛心得
- 【算法竞赛刷题模板17】二分法
- 数据结构和算法 二十一、贪心算法