汇编语言数组练习题两则

题目一:在数组中查找某数,查到则返回下标,查不到则返回-1
data段提供如下:

area array, data, readwrite
src    dcd 2,4,3,8,14,1,5
length equ 6*4
num    equ 3
dst    dcd -1,-1,-1,-1,-1,-1,-1

参考解答:

area search, code, readonly
       entry
start  mov r5, #num
       ldr r1, =src
       add r6, r1, #length
       ldr r3, =dst
       mov r4, #0

loop   ldr r2, [r1]
       cmp r2, r5
       BEQ output
inner  add r4, r4, #1
       add r1, r1, #4
       cmp r1, r6
       BLE loop
       B stop

output str r4, [r3]
       add r3, r3, #4
       B inner

Stop    MOV r0,#0x18
    LDR r1,=0x20026
    SWI 0x123456

end


题目二:数组匹配,给两个各自无重复数据的数组,查找里面匹配到的数据,把数据保存到另一个数组里。
data段如下:

area array, data, readwrite
src    dcd 2,4,6,8,10,12,14
len    equ 6*4
dst    dcd 1,2,3,4,5,6,7,8
length equ 7*4
array  dcd 0,0,0,0,0,0,0

参考解答:

area match, code, readonly
       entry
start  ldr r1, =src
       add r5, r1, #len
       ldr r2, =dst
       add r6, r2, #length
       ldr r7, =array

inner  ldr r3, [r1]
       ldr r4, [r2]
       cmp r3, r4
       BEQ output
       add r2, r2, #4
       cmp r2, r6
       BLE inner
outer  add r1, r1, #4
       ldr r2, =dst
       cmp r1, r5
       BLE inner
       B stop

output str r3, [r7]
       add r7, r7, #4
       B outer

Stop    MOV r0,#0x18
    LDR r1,=0x20026
    SWI 0x123456

区间调度问题

题目描述:

有n项工作,每项工作分别在si时间开始,ti时间结束。对于每项工作,你都可以选择参加或不参加,但选择了参加某项工作就必须至始至终参加全程参与,即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作,那么你最多能参与多少项工作呢?

限制条件:

1<=n<=100000

1<=si<=ti,=10^9


这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。

比较容易想到的算法如:

  • 在可选工作中,每次选取最先开始的工作
  • 在可选工作中,每次选取用时最短的工作
  • 在可选工作中,每次选取与最少可选工作有重叠的工作
  • 在可选工作中,每次选取结束时间最早的工作

而很显然,前三项算法都不具有普适性(例如:一项开头早,持续时间长的工作和两项开头晚的工作)。

关于最后一种算法的解释:

结束时间早,对应的可选工作就越多。当然也可以用归纳法来证明。

代码实现:

 

#include 
#include 
#include 
#include 
using namespace std;

const int N = 5;
int s[N]={1,2,4,6,8};
int t[N]={3,5,7,9,10};

int solve()
{
pair itv[N];
for(int i = 0; i 
	

栈是支持push和pop的数据结构。

push是在栈的顶端放入一组数据;pop是在栈的顶端取出一组数据。

Last in first out(LIFO):最后进入栈的一组数据会被最先取出.


 

样例:

 

#include
#include
using namespace std;
int main()
{
	stack s;//声明int类型数据存储的栈
	s.push(1);//『』→『1』
	s.push(2);//『1』→『1,2』
	s.push(3);//『1,2』→『1,2,3』
	printf("%dn",s.top());//3
	s.pop();//栈顶移除3,下同
	printf("%dn",s.top());
	s.pop();
	printf("%dn",s.pop());
	s.pop();//『1』→『』
	return 0;
}

返回栈顶元素:

// test_stack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include 
#include 
#include 
#include 

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	stack mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top()-=5;
	cout 
	

ACM刷题站精选

转自知乎——Luau Lawrence回答

此题回答与【国内有哪些好的刷题网站?】相同,为了方便阅读,都给出详细作答。

Welcome To PKU JudgeOnline 北京大学的Online Judge。POJ上面的题目有点老了,但好处是做的人多,经典算法题多,解题报告也多,适合上手。

ZOJ :: Home 浙江大学的Online Judge。ZOJ用的不多,但为数不多的几次体验好像都还可以,值得尝试。

Welcome to Hangzhou Dianzi University Online Judge 杭州电子科技大学的OJ。杭电OJ在近几年取代了POJ,成为是目前国内最主流的OJ。它的题目丰富,难度梯度合理,广受全国各大高校的青睐。每年也会有大大小小的比赛挂在杭电的OJ上举办,去年的亚洲区网络赛也是在这上面做的。由此可见其在国内广大ACMer心目中的地位。也正因为如此,网上hdu的解题报告也很多,适合个人进阶训练。

UVa Online Judge 西班牙Valladolid大学的Online Judge。是最古老也是全世界最知名的Online Judge,题库有详细的分类:如世界总决赛题目,刘汝佳的题目等等。题目目类型非常广泛。绝大部分的题目难度偏易,适合初学者磨练程序设计。

Timus Online Judge URAL是一个俄罗斯的在线题库。里面的题目相比国内一些OJ来说颇有些难度,我们学校集训队老队员喜欢拿这里的题出给新队员做,可见有一定的进阶作用。

Sphere Online Judge (SPOJ) SPOJ是波兰最为出色的Online Judge之一,界面和谐,题目类型也非常丰富,适合有一定基础的选手练习,对高手而言也是个提高能力的良好平台。传说君临天下的楼教主刷完了这个OJ?(更正:楼教主刷完的是SGU,感谢 @康Connor 指正)更多介绍见博客:SPOJ简介 – 海山

Saratov State University :: Online Contester 之前上SGU一直是404,所以不敢贴上来。现在亲测能上了就也放上来给大家看看吧。这个是货真价实的楼教主刷完的OJ。楼教主为什么要刷这个OJ而不刷这个回答里的其他OJ呢?因为这个OJ确实适合提升水平,应该跟Ural, SPOJ的难度相当。另外就不太了解了,在我心目中,SGU, Ural, SPOJ都适合区域赛冲金以及毕业想去Google等顶级公司的ACMer/Coder训练,三者区别不大。

Codeforces Codefores是俄罗斯的一个算法竞赛网站,由 Saratov State University 创办和维护。Codeforces主要强调的是算法竞赛,每隔1个礼拜左右就会有定期的线上比赛举行,其题库也是由每场比赛的题目一场场积累下来的。相比上面几个以题库为核心的OJ,Codeforces的算法竞赛比较适合锻炼自己的临场发挥和压力下编程能力。

HUSTOJ 华中科技大学的Online Judge。hustOJ也和主流的其他OJ一样有着丰富的题库。但它主要的用处,是它所提供的这么一个叫做vjudge的东西,全称叫做Virtual Judge。通过vjudge,你可以从各大OJ、包括但不限于上述的所有OJ中直接抽取题目,利用这些题目创建一个属于你自己的比赛。非常适合专题训练、日常集训以及小伙伴们一起比赛切题玩。

LeetCode Online Judge 与很多OJ不同,leetcode是一个主要面向面试者的OJ (LeetCode OJ is a platform for preparing technical coding interviews)。上面的题目不多,目前只有152道,很多都是许多大公司的面试题目。题目类型偏基础,基本不会考察复杂的算法,很多都是对基础知识的应用,难度与topcoder div1 250或codeforces div1 A题难度相当。如果是希望练习编程基础或准备公司面试的话非常推荐此OJ(感谢室友/集训队大神/CMU准硕士 @yun peng 同学提供Leetcode介绍)

计算机系学长的大学四年(转)

注:本文转自__Boost的CSDN博客,原文链接

1.极端的社会舆论

每每看到大学生就业报告里提到计算机系学生失业人数最多时,我就想mn,什么原因导致了这种现象的发生,在中国软件还处于比较初级的阶段时,市场对软件人才的需求应该每年在大幅的递增,可是大学里培养出来的计算机科班人才质量却每况愈下,甚至还不如一个软件培训机构两三个月训练出来的人好用,为什么?想想现在的计算机科班毕业生的水平吧,大学四年下来,90%的学生写的代码没有超过2000行,不Linux操作系统为何物,不知道C++和Vc的区别,没有开发出一块实用功能的简单软件,没有使用过STL,甚至不知STL为何物,更不用提设计模式之类的比较高级一点的东西了……这样的例子还能举出很多…

就是这样的人才质量,如何让一个以营利为目的的公司接受,如何为企业创造价值?但是也有那么一些人,能进入微软、IBM、google、百度这样的公司,拿着年薪几十万。

2.失败的计算机教育体制

我也是一名毕业不久的计算机科班毕业生,从我目前了解的情况看来,大学时,没有几个学生真正的对计算机编程感兴趣,体会不到通过编程解决问题带来的乐趣,只是单纯的跟着课程的设置学习,这样没有目的性的学习效率如何之底?大学里的学生又有几个人能对自己的职业规划有一个基本的了解?大学里有几个人能理解学习的课程在具体的实践中的作用?这些惨痛的例子说明了我们大学对计算机系学生的引导是非常不够的?没能激起对学习计算机技术的兴趣?不能告诉大家一个将来一个明确的职业规划方向,没有很好的引导学生去思考自己的职业规划方向?如果是这种状态去学习,大学四年基本是废掉了……

另外一个就是大学课程的设置,各种各样的课程,填鸭式的教学方式….纯粹理论式的教学方式….到头来,学生真正学到了什么?几个术语名词而已…..一样对操作系统是那样的迷茫….不知道编译原理的语法分析为何物?不知道数据结构中的树和图将有何用?

3.四年后,我能骄傲的说我是计算机系的学生

上面发了那么多的牢骚,其实都是有感而发….下面在结合自己的工作的感受具体谈谈计算机学生应该如何规划自己的大学四年

大一:

一个新兵蛋子,刚走进象牙塔的大门,什么都是新鲜的,不断听着学长们说着天书般的技术术语…天天争论C++和java哪个好,.net是否比Vc更智能先进…. 还有什么Asp.net …. 一堆的技术摆在自己面前了…

然后自己就糊涂了….去问学长吧…学长告诉你..好好学习java吧…将来有钱途…..

其实大一,没必要学习各种新鲜的技术…..把高等数学学好吧….这才是正事,是决定了着将来你是否能称为一个大牛还是一个编程语言的熟练操作工人的因素….也许这时候的你还不知道高等数学有什么作用…

但我要告诉你的是如果你的悟性高….工作一两年也许就能体会到数学的做用….学高数..不是简简单单的学习微积分….在掌握这些知识的时候….锻炼自己的逻辑思维….. 锻炼自己的思考问题解决问题的方法和能力。作用在将来一定大大的…..等将来如果你涉足密码学…你会发现各种积分方程和矩阵变化….将来在计算一个算法的复杂性和证明算法的可靠性时,也离不开数学知识….如果你涉足人工智能和语音识别,各种统计模型就会呈现在你面前。在你毕业找工作时,这个才是你和专业培训机构培训出来的学生的差异能力。这才是企业更看重的能力。如果你还有时间的话,学习C语言…但是不要再用谭浩强的书了…. 看

The C program langue吧… 如果能真正领悟书中70%的例子话,那就足够了. 如果能把这两门课程学到十分优秀,恭喜你,你已经成功了一半了…..

大二:

如果你在大一学习了C之后,这个时候大学的课程就要涉及操作系统和数据结构、还有汇编语言了……这也是大二一定要学好的两门课了……大学的操作系统太失败了,上完课后,很多的学生不知道所云,更加感觉操作系统的神秘了,课程设计也就是什么银行家算法的,然后大家在网上一顿搜索,然后交给老师就算完事了…

其实,我的建议是自己写一个操作系统内核,实现内存管理,进程管理和切换等一些基础的东西了就可以了,《自己动手写操作系统》就是很好的教材……如果还有时间,学习《Linux内核设计与实现》,看看现实商用的操作系统是怎么实现的?当然最好和原码结合的一起看,效果最好。还有赵炯博士的“.012Linux内核完全剖析”什么的。如果能仔细阅读,收获一定不少。当然还有数据结构,这个也是重中之中,这也是和非科班出身的学生的差别,关键是你学的好坏,这个的实践主要在ACM上,当学习完数据结构后,最重要的是使用,不断的在Acm上做各种各样的题目,不断的提升自己算法设计的能力。从大二开始,如果能坚持两年下来,那么一般的算法设计肯定是难不住的了,也许这时候高数打下的基础就会起作用了。

当毕业的时候,进入一家好的公司应该不是太难的事情了。再说说汇编语言,本质上这也是一门编程语言,可能刚入门的时候比较困难,但是程序写多了,和C也没有差别了。我还想说一点,就是现在Windows内核也逐步开放了,至少有很多的逆向的资源可以学习。如果对Windows有兴趣,一样可以学习操作系统的实现原理。

大三:

离散数学和编译原理是个重头戏,离散数学虽然我现在还没体会到他的作用,但是和高数一样,这中内在的东西才是最重要的,代表着内功,如果没有学好,这些债迟早还要要还的。编译原理,学习完以后一样会让你云里雾里,整天做那些无聊的题目。还是说实践吧,网上有开源的C编译器的源码,下载下来然后好好学习下,结合编译原理书中讲的东西,好好的消化一些这些知识,最后,自己如果能写出来一个C编译器的话,那你的编译原理也就通过了。当然这个时候可以学习一些C++或Java之类语言,但是学到够平时用的就可以了,没有学非常深。选择一本教材学习两三个月就行了。

当然,这个时候,可能你的同学已经能做出来各种漂亮的网页,也可能熟练的使用MFC类库做出各种各样的漂亮的软件,这些没什么,如果三年下来,如果你能够按照上面我写的那样坚持学习。也许他们用三年学习的这些东西,你用三个月就能熟练。

大四:

到了找工作的时候,如果你按照上面一步一个脚印的学习,我相信你会收到很多大公司的offer。因为大公司更看重的是你的内功的深厚,而小公司才会看重那些花拳绣腿的技术。但是这个时候,千万不要忘记继续学习,很多的学生大四一年都浪费掉了,真实太可惜了,在前面三年的基础上,到了厚积薄发的时候了,

开始要思考自己的职业规划了,你要选择Linux方向还是Windows方向,要选择底层方向还是应用方向,

要选择网页方向还是桌面应用方向。是选择自然语言处理还是人工智能。这个时候你要选择自己的一个方向,当然你可以向你的导师求助,然后确定自己的发展方向,大四一年就可以专心的学习了。

4.附上我认为计算机学习比较好辅助教材:

C语言: the C Program Language

操作系统; 于渊:《自己动手写操作系统》

《Linux内核设计与实现》

《Linux内核完全剖析》

《Linux内核情景分析》

《Windows内核情景分析》

编译原理:龙书《编译原理》

汇编:王爽老师《汇编第二版》

5.后记

以上都是自己在工作后对大学四年的反思,可能很多人有不一样的看法,我没有任何异议。毕竟每个人经历是不一样的,但是如果你向想做真正的计算机科班出身的学生,学好上面介绍的课程吧。在以后的职业生涯中,你会终身受益的。当然上面很多的课程我没有提到,并不代表他们不需要学习,只是分量没有那么重而已。因为你还是要毕业的,每门功课还是要过的。zds

当然,我现在认为,计算机的本科四年真是一个打基础的四年,之后才是学习各种招式,如果基础打好了,招式的学习会事半功倍的。当进入公司后,一样要持续不断的学习,才能让你不断的进步。自己文采不好,写的比较乱,但都是肺腑之言,各位将就看吧。

不需要辅助内存交换两变量

刚刚在林乐博客看到的,拿过来备用

用到的异或的方法:

#include "stdio.h"
int main()
{
    int a,b;
    while(scanf("%d %d",&a,&b)!=EOF)
    {
        a^=b^=a=a^b;
        printf("%d %dn",a,b);
    }
    return 0;
}

其实a^=b^=a=a^b;这句就相当于是

a=a^b;
b=a^b;
a=a^b;

写法.

除此之外还有加减法,代码:

a = a+b;
b = a-b;
a = a-b;

也可以方便的实现交换两数.

冒泡排序

今天看HDOJ2016的时候发现的冒泡排序算法。

算法原理:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每两个相邻元素作同样的工作,从第一个到最后一个。在这之后,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
#include
void main()
{
      int a[9],i,j,t;
      for(i=0;i

似懂非懂,继续看……