第一章_引论

2024-06-10 22:18
文章标签 第一章 引论

本文主要是介绍第一章_引论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原帖 http://m.blog.csdn.net/blog/warringah1/8871471

利用五一的空闲时间,看了下第一章的引论,网上都说这本书不错,看了第一章后感觉还好吧,至少不是在概念上的泛泛而谈,总有一点干货给你思考。

下面总结下引论的内容:

一开始就给出了两个例子:寻找第K大的数和字谜游戏。我对寻找第K大的数并不陌生,之前有编过线性时间找出第K大数的程序,偷笑中。第二个字谜游戏看似比较复杂,到时给出想法就不写代码了。

接下来是数学知识的复习,换底公式,级数求和,级数收敛,模运算,归纳法证明,反证法证明,这些都是之前有过接触过的知识,上手很快的。

最后一个是介绍了递归,个人感觉递归是个看似简单但用起来比较难的东东,但一旦用顺手了,能大大简化代码量增加可读性,但是不精心设计的递归有时也会拖垮CPU。记住几个法则吧:1.基准情形2.不断推进3.设计法则4.合成效益法则。注意第四个合成效益法则,就不担心会拖垮CPU啦。

最后给点干货吧,看此书不编程那不白看么~

 

1.1编写一个程序解决选择问题。令k=N/2。画出表格显示你程序对于N为不同值得运行时间。

书中给了两个解法,可都是O(n^2)运行时间的。第一个种解法是将这N个数读进一个数组中,再通过冒泡排序以递减的顺序将数组排序,最后输出第k位置上的元素。

<span style="padding: 0px; margin: 0px; font-size: 18px;">void BubbleSort(int arr[], int n)
{for (int i=n-1; i>0; --i) {for (int j=0; j<i; ++j) {if (arr[j]<arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}
</span>

第二种解法稍微好一点,可以先把前k个元素读入数组并以递减的顺序对其排序,剩下的元素再逐个读入,当新元素被读到时,如果她小于数组中的第k个元素则忽略,否则将其放在数组中的正确位置上,同时将数组中的一个元素挤出数组。细想想,这种解法是冒泡排序和插入排序的一个合体,当k=1时就退化为插入排序,本质上没有时间上的优化。

<span style="padding: 0px; margin: 0px; font-size: 18px;">int SortKMethod(int arr[], int n, int k)
{int *tempArr = new int[n];memcpy(tempArr, arr, sizeof(arr)*n);BubbleSort(tempArr, k);for (int i=k; i<n; ++i) {if (tempArr[i]>tempArr[k-1]) {for (int j=0; j<k; ++j) {if (tempArr[j]<tempArr[i]){for (int m=k-1; m>j; --m)tempArr[m] = tempArr[m-1];tempArr[j] = tempArr[i];break;}}}}int result = tempArr[k-1];delete[] tempArr;return result;
}
</span>

第三种解法就比较巧妙。还记得算法导论上快速排序那一讲么?有个很经典的程序叫Partition。我觉得这个经典的程序应该背住在脑海里,因为它的思想很经典而且程序很精巧。它的作用是以数组中最后一个元素为基准,前面的元素都是大于它的,后面的元素都是小于它的,但是它前后的元素不一定按顺序排列。这样一来,不管它前后的元素怎么排列,它的位置总是固定下来了。它前面恰有k-1个数,那第k大的不正是它么?它的运行时间是O(n),线性时间。有人会问,为什么选择最后一个数作为基准,当然这不是一定的,你也可以选择第一个数,中间一个数,甚至是编一个随机数算法进行随机选择,这样,对极端的输入你的程序也不会运行时间太糟,这个我就不展开了,可以参考算法导论那一章,或者July大神的博客,一定会有收获的。

这时结合之前递归的思想,若你选取的基准数恰好是第k个数,则返回它本身,若它的位置为q(小于k),说明你应该对后一部分做递归,但是,应该选取后一部分的第k-q个位置;若它的位置为p(大于k),则还是对前一部分做递归,但应该选择前一部分的第k个位置。好了,这应该是很简单的,被我说复杂了没直接上代码:

<span style="padding: 0px; margin: 0px; font-size: 18px;">int Partition(int arr[], int p, int r)
{int x = arr[r];int i = p - 1;//i保存的是大于x的数的下标for (int j=p; j<=r-1; ++j) {if (arr[j]>x) {++i;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[r]);return i+1;
}int LinearSelectK(int arr[], int p, int r, int k)
{if (p==r)return arr[p];int q = Partition(arr, p, r);int m = q - p + 1;if (m==k)return arr[q];else if (m<k)return LinearSelectK(arr, q+1, r, k-m);elsereturn LinearSelectK(arr, p, q-1, k);
}
</span>

第一题大概就是如此了。有更好的想法或者有待改进的地方,请不吝留言啊,大家一起讨论。

 

1.2编写一个程序求解字谜游戏问题。

这个问题看着就觉得比较复杂。想了下如果按照书上的提示做for循环那不把自己绕晕了。参考了下网上的思路,有一点我比较同意,就是遍历前也需要建立文件存放所有单词的所有前缀。然后遍历。下面是摘自http://blog.csdn.net/golden_shadow/article/details/5972867一段话,大家可以去参考。

“思想,就是,记录下单词的所有前缀,这样可以减少扫描次数.我的实现方式,新建一个文件存放所有单词的所有前缀,之后同单词一起装进表中.添加一个指示域来指示表中的字符串是单词还是前缀.之后在主循环中先进行单词判断,而后进行前缀判断.如果当前的字符串不是单词并且也未作为前缀出现在表中,那么就跳出当前方向的循环.”还有就是据说用Trie树解决比较方便,对Trie树我没有详细研究过,有同志可以详细讲讲么?

 

1.3只使用处理I/O的PrintDigit函数,编写一个过程以输出任意实数。

一开始我的想法很简单,由于有了PrintOut这个函数,我们就可以利用它来输出一个double类型的数,只要知道小数点所在的位置,就可以用PrintOut这个函数分别输出整数部分和小数部分。例如123.456,先用int方法取整得到123,PrintOut输出,然后将0.456乘以1000得456,再利用PrintOut输出。求小数点的位置不是很难,我想可以利用double转成string类型,find小数点的位置,再找到小数点到最后一个数的长度就行了。利用pow函数就能得到456。这个想法想起来很容易,但是其实是有问题的。因为计算机精度的问题,double在计算机里不能精确的存储,比如0.456可能在计算机里是以0.45599999999…的方式存放的。这样就比较尴尬了,可能需要四舍五入等等,就比较麻烦,大家有什么好想法?至于负数就很好处理,判断是负数后输出“-”,然后区反当成正数处理就是了。上代码,小数点的位置我就当输出参数输进去了。

<span style="padding: 0px; margin: 0px; font-size: 18px;">#include <iostream>
#include <cmath>
using namespace std;void PrintDigit(unsigned int i)
{cout<<i;
}void PrintOut(unsigned int i)
{if (i>=10)PrintOut(i/10);PrintDigit(i%10);
}void PutOut(double n, int d)
{if (n<0) {cout<<"-";n = -n;}int integerPart = int(n);PrintOut(integerPart);if (n!=integerPart) {double fractionPart = n - integerPart;cout<<".";int scaled = fractionPart * pow(10.0,d);PrintOut(scaled);}}
int main(int argc, char **argv)
{PutOut(-123.34,2);system("pause");return 0;
}
</span>

1.4C提供形如#includefilename的语句,它读入文件filename并插入到include语句处。include语句可以嵌套,换句话说,文件filename还可以包含include语句,但是显然一个文件在任何链接中都不能包含它自己。编写一个程序,使它读入被include语句修饰的一个文件并输出这个文件。

一眼看到这个问题就想到马士兵讲过的java教程里有个输出文件名字的例子,文件里嵌套文件,和这个有点像,不用递归用什么???

但是要处理自身包含的问题,我的想法是建立一个list,将每次输出的filename存入,但是存入前先要看看list中有没有,若有则存在自身包含的问题。这个list可以用最经典的~~~~容器~~~~来解决,不错,就是set容器,这个容器的特点是每个元素的值是唯一的,当只想知道一个值是否存在时,使用set容器最合适(摘自C++Primer),它有个count运算可以在set容器中查找是否有这样一个值存在。

在编代码时,发现我对一些容器(set,string等)的操作还不是很熟悉,对问价的操作也不是很熟练,好吧,四个月不碰c++果然是生疏了。Labview用多了也会让人对c++编程产生生疏感。

在编程时遇到一个让我很纠结的问题,在定义set<string> fileNameSet;前我包含了#include <cstring>和#include <set>,但是编译老是出错(error C2784: “boolstd::operator <(const std::_Tree<_Traits>),我理解的意思是因为set中涉及到了排序的操作所以在重载<操作符,但是cstring文件里可能就没有重载它。我换成了#include <string>后这个问题就消失了。后来查了一下cstring和string文件的区别,网上是这么说的,cstring和string.h差不多,一个是c++版本的头文件,一个是c版本的头文件。里面都包含了诸如strcpy之类的字符串处理函数,而string,包含了std::string的定义,属于STL范畴。所以用到string容器我当然要包含string了!不然编译器就不认识string!!上代码。

<span style="padding: 0px; margin: 0px; font-size: 18px;">#include <iostream>
#include <fstream>
/*#include <cstring>*/
#include <string>
#include <set>using namespace std;set<string> fileNameSet;
void ProcessFile(const char* FileName)
{ifstream fin;fin.open(FileName);if (!fin) {cerr<<"error:unable to open input file:"<<FileName<<endl;return;}fileNameSet.insert(FileName);cout<<FileName<<endl;char str[50];while (!fin.eof()) {fin.getline(str,50);string strLine = str;string constStr("#include ");if (strLine.find(constStr)==strLine.npos)break;else {string fname = strLine.substr(constStr.length()+1,strLine.length()-constStr.length()-2);if (fileNameSet.count(fname)==0)ProcessFile(fname.c_str());else {cerr<<"Self-referential includes is detected:"<<fname<<endl;return;}}}fin.close();}int main(int argc, char **argv)
{ProcessFile("A.txt");system("pause");return 0;
}
</span>

好了,四道编程题就这样了,以纪念我五月的第一天大早就开始写博客,写博客花的时间比编程还多啊,果然是苦差事,但是把自己的思路整理一下并和别人分享也是快乐的~


这篇关于第一章_引论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1049417

相关文章

【自然语言处理】第一章绪论

第一章 绪论 文章目录 第一章 绪论1. 什么是自然语言2. 自然语言处理的定义2.1 自然语言处理NLP2.2 计算语言学CL2.3 NLP与CL 3. 自然语言处理的研究内容3.1 研究对象3.2 研究层次3.3 研究问题3.4 研究内容3.4.1 资源建设3.4.2 基础研究3.4.3 应用技术研究3.4.4 应用系统 4. 自然语言处理的流派5. 自然语言处理的挑战

第一章 MUD:创造世界的巫师

自从有了游戏之后,人们不满足于做屏幕前的操控者,而是梦想着自己能够进入到游戏的绚丽世界中,在剑与魔法的世界中拯救世界,称为吟游诗人歌颂的屠龙 勇者,或者在武侠世界中快意恩仇,体验江湖恩怨儿女情长。网络游戏的出现让这个梦想渐渐变为可以触摸的东西,直至成为现实。   如果要追溯网络游戏的历史,我们要将目光投向20世纪70年代。早在1969年,美国人瑞克•布罗米(Rick Blom

第一篇 第一章资金时间价值计算及应用 第二章经济效果评价

第1章 资金时间价值计算及应用 资金具有时间价值 1.1 利息的计算 1.1.1 利息和利率 I=F-P 债务人为资金需求方 债权人为资金供给方利息对经济活动的影响(1.影响企业行为 2.影响居民资产选择行为 3.影响政府行为) 利率 1.影响因素(1.社会平均利润率的高低 2.市场资金供求对比状况 3.资金要承担的风险 4.债务资金使用期限长短 5.政府宏观调控政策 6.经济周期所处

第一章 软件工程的概述简记

第一章  软件工程的概述         *软件的概念:软件(Software)是一系列按照特定顺序组织的计算机数据和指令的集合。         软件的分类:(5大类)                   *1.基于软件功能划分                                  1)系统软件

第一章——计算机系统概述

🌈个人主页:小新_- 🎈个人座右铭:“成功者不是从不失败的人,而是从不放弃的人!”🎈 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 🏆所属专栏: 计算机组成原理   欢迎订阅,持续更新中~~~                                                       ✨让小新带着你快乐的学习吧~✨ 目录 前言 一、操作系统的概念和

第一章 感受mac之美-换一种方式用电脑,开启新历程

感谢关注我的读者一直以来的追随与信任。去年到今年以来大环境都不是很好。裁员,机构优化,工厂倒闭,公司破产,贸易战等消息传来,不少还是身边发生的。今年开年以来更是有病毒横行,天降蝗灾等灾害。愿大家都好好的,同时希望这场战役早早告捷。今天是二月二 ,民间传说龙抬头,祝愿大家从此事业腾飞,从此出人头地。 我在这断更的两年中的一些情况,一直处于闭关的状态,一直在学习与实践。后续再和大家一起分享这俩年

考研408《计算机组成原理》复习笔记,第一章计算机系统概述

本人打算从今到2026年不再更新过多的前后端开发的笔记,因为要准备考研了,所以停更前面的开发教程。 这些都是我看完书、视频、做完题后,结合个人理解总结的知识点,希望对各位有帮助。一切都是用最快最精炼的方式讲清楚。 一、计算机发展历程 第一代:电子管时代第二代:晶体管时代第三代:中小规模集成电路时代第四代:超大规模集成电路时代 就这么记就行了,很少考你历程这些细节的。 二、计算机系统结

【软件工程】第一章软件工程引论

【软件工程】第一章软件工程引论 文章目录 【软件工程】第一章软件工程引论1. 什么是软件1.1 软件的定义1.2 软件特征1.3 挑战与危机 2. 什么是工程2.1 什么是工程2.2 怎么做工程 3. 什么是软件工程3.1 软件工程的提出3.2 软件工程的经典定义3.3 软件工程设计的知识域3.4 系统工程3.5 软件工程的全流程 4. AI时代的软件工程4.1 智能软件工程4.2 大模型

《软件工程导论》(第6版)第9章 面向对象方法学引论 复习笔记

第9章 面向对象方法学引论 一、面向对象方法学概述 1.要点 面向对象方法学已经成为人们在开发软件时首选的范型。面向对象技术已成为当前最好的软件开发技术。 (1)基本原则 面向对象方法学的出发点和基本原则,是尽可能模拟人类习惯的思维方式,使开发软件的方法与过程尽可能接近人类认识世界解决问题的方法与过程,使描述问题的问题空间(问题域)与实现解法的解空间(求解域)在结构上尽可能一致。 (2

计算机网络: 第一章 概述_3:计算机网络的体系结构

文章目录 1. OSI模型(开放系统互联模型)2. TCP/IP模型3. 三种体系结构4. 计算机网络体系结构分层的必要性5. 计算机网络体系结构分层思想举例6. 计算机网络体系结构中是专用术语练习题练习题答案 计算机网络体系结构是指计算机网络设计和实现的框架和规范,它包括不同层次和组件的组织方式。常见的计算机网络体系结构有两种主要模型:OSI模型和TCP/IP模型。