寒假总结

发布在 杂谈

颓废的大二上之后感觉良好的一个寒假,可能是我自上学以来效率最高的一个寒假了。

学习

LeetCode

大二上刚开学的时候因为数据结构上到链表和树的缘故,在LeetCode上刷了20多道Tag是链表和树的题目。

寒假的时候决心开始刷LeetCode,至寒假结束时已经完成了126道题,其中包括了绝大部分Easy题,以及少部分Medium题,虽然和真正学好算法相差甚远,应该算是基本上入门了。

主要接触了分治法以及相关的复杂度分析,哈希表,随机化相关的算法(蓄水池抽样以及FisherYales洗牌算法),简单的动态规划等。

通过的题目以及解法托管在我的Github上。

Python爬虫入门

参考书是《Python网络数据解析》,目前看到了第三章,主要接触了urlopen以及BeautifulSoup库以及最基本的爬虫思想,原书第三章的最后也简单的提到了爬虫用的Scrapy框架。

学习时候练习的代码托管在我的Github上。

MIT的算法导论公开课

目前看到了“快速排序以及随机化算法”这一节,但是对于之前所重点介绍的分治法的主定理仍然有不清楚的地方,需要花时间巩固学习并且配合LeetCode一起食用。

数据结构课程设计

因为其他事情的原因,我选的是最简单的第三题“基于查找表的单词检索软件”,但是我并没有使用二叉搜索树而是使用了Trie树来实现动态查找表。

抱着既然要做课设就不要糊弄的想法,这次的课设还是浪费了自己不少时间,在完成了最基本的Trie树以及Hash表之后,自己又实现了Hash表的迭代器以及Hash表的序列化,了解到了C语言中命令行参数的处理 - getopt。虽然程序仍然有大量可以优化和改进的地方,但是考虑到今年寒假投入的时间不是特别多,我总体上来说还是很满意的。


虽然说了不立Flag,写寒假总结督促自己,但是实际上今年寒假还是有各种堕怠,想要做的事情还是有很多没做,想想还是有点遗憾,但毕竟还是比大二上和去年寒假要好很多了。


关于输入和输出:仅对于自己而言,我认为输入和输出都是必要的,如果只强调输入,而忽视输出,那么只知道知识本身而不会运用知识,于我而言会失去学习的兴趣,更何况在大多数时候,缺乏一定数量的练习的我们甚至还没有能真正的掌握知识;而如果是以为的强调输出,那么可能和大一的我一样,只能成为为一个劣质的API Caller而已。


想到了去年团队总结说过的话,同样送给今天的自己:身为一个本科生,在扎实自己计算机基础的同时我也愿意更多的接触不同的方向比如iOS,Web的前端、后台技术甚至是一些设计的规范(世界这么大,我想去看看)。未来自己还要更加努力才行啊(毕竟现在的基础还是很弱)。

生活

大二上因为种种原因而陷入了迷茫,加权没有刷上来,在自己想学的东西上也几乎没有花什么时间,一直在懒懒散散地混日子,生活更是一团糟,但是好在并没有做出让自己后悔的事。

寒假刚开始的时候想了很多,虽然前路漫漫,伤痛注定多余喜悦,但我也决定不再逃避过去的自己,正视现在的自己。假期的时候和很多曾经的同学交流过人生和发展,也终于鼓起勇气认识了更多的人,看到了更多不一样的人生。然后这样的自己,突然又获得了梦想。

每一个不曾起舞的日子都是对生命的辜负,以上。

评论和共享

KMP算法是著名并且高效的字符串匹配算法,该算法因Knuth,Morris与Pratt三人联合发表而得名。

问题

给定两个字符串S(n个字符)和W(m个字符),求W在S中第一次出现的位置。

BF(Brute Force)算法

BF算法是普通的模式匹配的算法,该算法的思想是首先比较S和W的第一个字符,若匹配,则继续比较下一个字符,若不匹配,则从S的第二个字符和W的第一个字符开始,重复上述过程,直到S和W匹配。

该算法的时间复杂度为 O(m*n)

KMP(Knuth-Morris-Pratt)算法

算法思想

在BF算法中,如果发生字符串失配,那么我们会从S的下一个字符开始重头开始匹配,而实际上,在发生失配时,W自身已经包含了足够的信息,以确定下一个匹配的位置,这就是KMP算法的核心思路。

算法实例

不妨设字符串S为 ABC ABCDAB ABCDABCDABDE,W为 ABCDABD

首先我们从W和S的开头开始匹配,但是我们发现,S[3] = ‘ ‘而W[3] = ‘D’,发生了失配,但我们同时也发现,S[1]到S[3]不与W[0]——也就是’A’相匹配,因此下一次匹配我们直接从S[4]开始,与W[0]进行匹配。

1
2
3
4
      |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|
1
2
3
4
       |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|

随后,我们发现S[10] = ‘ ‘与W[6] = ‘D’失配,注意到W[0]-W[1]与W[4]-W[5]均为”AB”,因此下一次匹配时,我们也不必直接从下一位开始匹配,而是可以从已匹配的尾部的”AB”处继续匹配。

1
2
3
4
             |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|
1
2
3
4
             |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|

下图所示的情况与上述的情况类似,我们直接从尾部的”AB”处继续匹配。

1
2
3
4
                    |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|
1
2
3
4
                    |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|

最终找出了完全匹配的位置。

1
2
3
4
                        |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
|

部分匹配表(失配函数)

部分匹配表中的部分匹配值指出了在发生失配时,可以跳过的无效字符数。

我们首先需要了解两个概念:“前缀”和“后缀”。

“前缀”指除了最后一个字符之外,一个字符串的全部头部组合;“后缀”指除了第一个字符之外,一个字符串的全部尾部组合。

部分匹配值就是“前缀”和“后缀”的最长的共有元素的长度。

部分匹配值的实质是,有时候,字符串的头部和尾部会有重复。这样,不能直接将字符串向后移动“字符串长度”位,而是应该移动“字符串长度-部分匹配值”位。

部分匹配表实例

以”ABCDABD”为例——

  • “A”的前缀和后缀都为{},共有元素长度为0;
  • “AB”的前缀为{“A”},后缀为{“B”},共有元素长度为0;
  • “ABC”的前缀为{“A”, “AB”},后缀为{“C”, “BC”},共有元素长度为0;
  • “ABCD”的前缀为{“A”, “AB”, “ABC”},后缀为{“D”, “CD”, “BCD”},共有元素长度为0;
  • “ABCDA”的前缀为{“A”, “AB”, “ABC”, “ABCD”},后缀为{“A”, “DA”, “CDA”, “BCDA”},共有元素为{“A”},长度为1;
  • “ABCDAB”的前缀为{“A”, “AB”, “ABC”, “ABCD”, “ABCDA”},后缀为{“B”, “AB”, “DAB”, “CDAB”, “BCDAB”},共有元素为{“AB”},长度为2;
  • “ABCDABD”的前缀为{“A”, “AB”, “ABC”, “ABCD”, “ABCDA”, “ABCDAB”},后缀为{“D”, “BD”, “ABD”, “DABD”, “CDABD”, “BCDABD”},共有元素长度为0;

算法实现(C语言)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int kmp (const char * s, const char * w) {
int s_idx = 0;
int w_idx = 0;
int s_len = strlen(s);
int w_len = strlen(w);
int next[w_len];
generate_next(w, next);
while (s_idx < s_len && w_idx < w_len) {
if (w_idx == -1 || s[s_idx] == w[w_idx]) {
s_idx++;
w_idx++;
} else {
w_idx = next[w_idx];
}
}
if (w_idx == w_len) {
return (s_idx - w_idx);
} else {
return -1;
}
}

void generate_next(const char * w, int * next) {
int index = 0, k = -1;
int w_len = strlen(w);
next[0] = -1;
while (index < w_len -1) {
if (k == -1 || w[index] == w[k]) {
++k;
++index;
next[index] = k;
} else {
k = next[k];
}
}
}

算法分析

注意到这里我们对于部分匹配表做了一些额外的处理,我们将部分匹配表的值向右移动了一位,并且将部分匹配表的第一个值置为了-1。

这是因为字符串w的第一个字符串的特殊性决定的,因为w字符的第一个字符串失配后无法回退,只能从s字符串的下一个字符开始匹配。

此外,在求解next数组的函数generate_next中还有一句k=next[k],这实际上是字符串的自我匹配的过程,当0–k-1发生失配时,应当找到一个满足条件的j,从0–j-1之后继续匹配,直到找不到更小的字符串为止。

算法复杂度

O(m+n)

参考

从头到尾彻底理解KMP

【经典算法】——KMP,深入讲解next数组的求解

克努斯-莫里斯-普拉特算法

后记

一直不能够深刻地理解KMP算法,即使是写完了这篇Blog,我仍然对于KMP算法有着有限的了解,所以不排除这篇Blog还会有后续的可能。

评论和共享

OSTEP学习笔记1

发布在 操作系统

最近开始看Operating Systems: Three Easy Pieces这本书,感觉光看书还是不够,还是需要将学习到的东西整理和归纳,以加深自己对于操作系统的理解。

CPU的虚拟化

基本概念

进程

进程(Process)是操作系统对于一个正在运行的程序的抽象

进程API

大体上可以分为创建(Create),销毁(Destroy),等待(Wait),杂项控制(Miscellaneous Control)包括挂起等以及状态查询(Status)。

Unix下的进程API

fork() wait() 以及 exec()

进程状态

进程的状态大体上可以分为运行(Running),就绪(Ready)以及阻塞(Blocked)。

  • 运行(Running),进程正在被处理器运行,这意味着,处理器正在执行指令。
  • 就绪(Ready),进程已经准备好去运行,但是出于某种原因,操作系统决定不在当前的时刻运行该进程。
  • 阻塞(Blocked),在阻塞状态,进程已经执行了某种其他的操作以至于在该操作完成前该进程不能就绪,如:进程对于磁盘的IO请求。

进程表

操作系统通常会使用进程表管理所有的进程,包括追踪每一个进程的寄存器,起始内存,内存大小,PID,父进程,已打开的文件,进程状态等。

机制:Limited Direct Execution(LDE)

直接执行即系统直接将进程运行在CPU上以最大化效率,限制即不能直接让进程取得对硬件以及系统所有的控制。

限制操作

当进程需要执行IO请求等限制操作时,不应该使得进程获得整个操作系统的控制权限。因此引入了Protected Control Transfer的概念。

Protected Control Transfer

引入两种处理器模式:User ModeKernal Mode

  • User Mode - 在User Mode下,运行在该模式下的代码受到了严格的限制。比如,在该模式下,进程无法发起IO请求,并且也无法执行所有的限制指令。
  • Kernal Mode - 在Kernal Mode下,由操作系统执行指令,执行的指令没有任何限制,包括IO请求以及所有的限制指令都可以被执行。

System Call - 用户程序通过执行System Call去执行限制指令如访问文件系统,与其他进程通信或是分配内存。
为了执行System Call,用户程序需要执行一个特殊的Trap指令,Trap指令同时地跳转至内核并且提升至Kernal Mode,一旦进入了内核,系统就可以执行任何限制指令,并且完成调用进程需要完成的任务。完成后,系统调用一个特殊的Return-From-Trap指令,跳转回用户程序并且降低至User Mode。

在执行Trap指令时,系统需要额外的开销以保证执行Return-From-Trap指令时跳转正确,例如,在x86下,系统会将PC及其他几个寄存器存入每个进程的内核栈。

此外,内核需要在引导时建立Trap Table以保证用户程序程序执行Trap指令后能跳转至对应的指令。操作系统通知硬件Trap Handlers的位置,通知之后,直到下次引导之前,硬件都会知道对应handlers的位置,这样,当System Call或是其他异常被抛出时,硬件能对应作出正确的反应。

显然,建立Trap Table的指令也是限制指令。

进程间切换

进程的切换需要操作系统的介入,但是当用户程序在CPU上执行时,操作系统并不在运行,那么,操作系统要如何重新获得对CPU的控制呢?

合作方法:等待System Calls

在这种方法下,操作系统相信系统进程能正确的执行,长时间运行的进程理应周期性的放弃CPU,从而操作系统能决定运行其他的任务。

大多数进程通过发起System Calls的方法转移CPU的控制权 - 在发起System Call,执行了Trap指令后,操作系统就获得了CPU的控制权。

那么,当程序错误的执行死循环之后,操作系统还能拿到CPU的控制权吗?

非合作方法:系统直接控制CPU

Timer Interrupt - 通过对定时器装置编程使得其每隔特定的时间(通常是毫秒级)发起中断。在这种情况下,当前执行的进程会被停止,并且操作系统中一个预先配置的Interrupt Handler会被执行,这样,操作系统就重新取得了对CPU的控制。

保存和恢复上下文

通常,当系统决定切换进程时,操作系统会执行一段底层代码(Context Switch)。从概念上来说,Context Switch会保存当前进程的若干寄存器的值,并且恢复待执行的进程的寄存器的值(例如,从内核栈中),这样,当Return-From-Trap指令执行时,系统得以恢复另一个进程的运行。

在Timer Interrupt的LDE Protocal中(例如),存在着两种类型的寄存器保存/恢复,在中断产生时,由硬件隐式的将寄存器的值存入当前进程的内核栈中,而在操作系统决定从当前进程切换至待执行进程时,由软件(操作系统)显式的将当前进程的寄存器的值(如PC,栈指针)存入当前进程的进程结构中(例如,进程控制块),并且从带切换进程的进程结构中恢复对应寄存器的值,这样,当执行Return-From-Trap指令后,由硬件隐式的从切换进程的内核栈中恢复寄存器的值,就好像刚才的Trap是由切换后进程执行的一样。

并发性

如果当一个System Call被发起时,发生了一个Timer Interrupt怎么办?

简单的做法是,在处理中断时,禁止其他中断的传入。更加复杂的机制留至并发行部分讨论。

调度器

负载假设

将正在运行在系统上的进程称为负载。为了简化调度过程,首先做出如下的假设:

  • 每一个任务(Job)运行同样的时间
  • 所有的任务都在同样的时间到达
  • 所有的任务都仅使用CPU(不执行I/O)
  • 每一个任务的运行时间都已知

我们会在稍后的讨论中放宽这些限制

调度指标

我们用调度指标衡量调度器的好坏,我们将使用以下两个指标:

  • 周转时间(Turnaround Time) 周转时间是指完成时间与到达时间的差,周转时间是衡量性能性能的指标。
  • 响应时间(Response Time) 响应时间是指任务第一次运行的时间与到达时间的差,响应时间是衡量公平性的指标。

先进先出(First In First Out)

该调度方法有时又被称作先到先得(First Come First Served),即先到达的方法先被CPU运行。

假设有3个任务,每个任务都运行10s,那么它们的平均周转时间为(10+20+30)/3=20s
下面我们放宽假设1,即现在每一个任务运行的时间不必相同。

同样地,假设有3个任务,A运行100s而B和C运行10s,如果A先运行,然后运行B,最后运行C,那么现在的平均周转时间为(100+110+120)/3=110s,这就是护送效应(Convoy Effect),即由于A的运行时间过长,而导致运行时间较短的B和C需要等待较长的时间。

提出如下的新规则——

最短任务优先(Shortest Job First)

为此,我们提出一种新的规则称为最短任务优先,该规则同样易于理解,即首先执行最短的任务,然后次短的任务,以此类推。

同样地假设A、B、C三个任务,其中A运行100s,而B和C运行10s,在SJF下,系统会先运行B和C,再运行A,平均周转时间为(10+20+120)/3=50s,远好于FIFO下相同假设的结果。

下面我们放宽假设2,即每一个任务有可能在任意时间到达。

假设A、B、C三个任务,其中A运行100s,在0s时到达,B和C运行10s,在10s时到达,在SJF下,平均周转时间为(100+(110-10)+(120-10))/3=103.33s,这是我们不愿意看到的结果,我们仍然需要改进调度算法——

最短完成时间优先(Shortest Time-to-Completion First)

SJF是一种非抢占(Non-preemptive)的调度器,而STCF是一种允许抢占的调度器,在上述的例子中,当B或者C到达时,调度器允许B或者C抢占A——即操作系统从任务A切换至任务B或者任务C(通过上下文切换),从而达到提升性能的目的。

在上例中,若采用STCF,平均周转时间为((120-0)+(20-10)+(30-10))/3=50s,远好于103.33s这一结果。

事实上,如果任务长度已知,任务仅使用CPU资源,且周转时间是唯一指标的话,STCF是最佳的调度算法,下面我们来讨论另一个指标——响应时间。

考虑到响应时间,上述的算法表现都不尽如人意,在上例中,用户要至少要等待10s才能得到任务C的响应,而这显然是对于交互不友好的,我们需要引入新的调度算法来解决这个问题——

轮循(Round Robin)

轮循的基本思想按照时间分片(Time Slice)或者说调度量子(Scheduling Quantum)来循环执行任务而不是运行任务直到完成。

假设有A、B、C三个任务,它们同时到达系统而且均运行5s,假设时间分片为1s,在这种情况下,操作系统首先运行A,1s后切换到B,B运行1s后再切换到C,然后再循环回A。这样,平均响应时间为(0+1+2)/3=1s;而在SJF下,平均响应时间为(0+5+10)/3=5s。

需要权衡时间分片的大小,如果时间分片过小,那么操作系统执行上下文切换的开销会显著增加。

在RR下,平均周转时间会变得非常糟糕。事实上,公平性和性能在调度中是矛盾的,任何注重公平性的调度算法(即拥有良好的响应时间)在性能上(即周转时间)都会表现的很差。这是固有的权衡,鱼和熊掌不可兼得

合并I/O

接下来我们放宽假设3,即任务除了使用CPU外,还可能执行I/O请求,在发起了I/O请求后,任务将不会使用CPU,并且将处于阻塞的状态以等待I/O完成。

调度器需要决定I/O请求启动时是否切换至另一个任务,以及I/O完成时是执行当前任务还是切换回之前阻塞的任务。

假设我们正试图建立一个STCF调度器,假设A和B两个任务均运行50ms,并且A每10ms会发起一个花费10ms的I/O请求。在这种情况下,通常的解决方法是将A划分为5个独立的子任务,这样,当A发起I/O请求并且阻塞之后,B就可以被执行,而当I/O完成后,新的A的子任务会抢占B而继续执行。

上述的做法允许了重叠(Overlap)的发生,系统得以更好的利用处理器资源。

多级反馈队列(Multi-Level Feedback Queue)

最后,我们将放宽限制4,即系统不知道每个任务的运行时间。在这种情况下,我们将引入最有名的调度器之一——多级反馈队列来解决该问题。多级反馈队列试图在提升性能(即缩短平均周转时间)的同时最小化任务的响应时间。首先,我们将介绍有关多级反馈队列的最基本的概念。

MLFQ:基本规则

多级反馈队列(MLFQ)具有一系列相互独立的队列(Queue),每一个队列都对应着不同的优先级(Priority Level),在同一时间,一个任务只会处在一个队列中。

MLFQ根据优先级决定运行哪一个任务:即具有更高优先级的任务会被运行。

同时,考虑到可能会有多个任务处于同一个队列,即有可能出现相同优先级的情况,在这种情况下,MLFQ以轮循的方式运行这些任务。

因此我们得到了如下的基本规则:

  • 如果A的优先级大于B的优先级,运行A(B不运行)
  • 如果A和B的优先级相同,以轮循的方式运行A和B

假设两个任务A和B,A和B位于最高的优先级,而C和D位于次高的优先级,那么我们会发现,A和B会一直被运行,而C和D将永远无法被运行。

尝试1:如何改变优先级

MLFQ依据已经观察到的结果确定一个任务的优先级:如果一个任务在一个相当长的周期内一直在使用CPU,那么MLFQ会降低它的优先级,如果一个任务周期性的放弃CPU而等待用户的输入,那么MLFQ会维持它的优先级,因为这样的任务是一个活跃的任务。

因此我们得到了如下的规则:

  • 当一个任务进入系统时,它将会被放置在优先级最高的队列
  • a如果一个任务在运行中占用了一个完整的时间分片,那么它的优先级会被降低
  • b如果一个任务在时间分片用完前放弃了CPU,那么它的优先级维持不变

在上述的规则中,我们考虑如下的两个问题:

  • 如果有太多的活跃任务,那么他们会占用所有的CPU时间,那么,长时间运行的任务将永远不会得到任何的CPU时间。
  • 程序可以以在时间分片用完前“故意”地放弃CPU以欺骗操作系统而使得其保持高优先级
尝试2:优先级提高

我们引入如下的规则来解决上面提到的问题1:

  • 在某个时间周期S之后,将系统中所有的任务提升至优先级最高的队列

通过该规则,过多的活跃进程并不会完全占用CPU的时间,此外,当一个程序从不活跃转变为活跃时也能够及时得得到响应的CPU时间。

尝试3:更好的计量

我们引入如下的规则来解决上面提到的问题2:

  • 一旦某个任务用完了在给定优先级下的分配时间,无论它已经放弃了多少次CPU,降低它的优先级。

这么做避免了一个任务欺骗操作系统,避免了其通过不公正的手段分享CPU的时间。

评论和共享

iOS学习笔记(三)

发布在 iOS开发

花了两天半的时间基本实现了APP中让用户选择头像的功能(仿照手机版QQ),整理和总结如下——

思路

- UIImagePickerController


原先想要采用UIImagePickerController来实现这个功能,UIImagePickerController是UINavigationController的子类,是系统提供的拍摄、选择照片和视频的UI。具体来说,在选择头像这个功能中,头像的来源有两种——拍照和从相册选择,同时完成头像的选择后我们还应该能够让用户选择头像的范围以及大小。

若头像的来源为拍照:

1
2
3
4
5
6
UIImagePickerController * imagePickerController = [[UIImagePickerController alloc]init];
imagePickerController.delegate = self;
imagePickerController.allowsEditing = YES;//允许编辑图片
imagePickerController.sourceType = UIImagePickerControllerSourceTypeCamera;//图片的来源为相机
//...还可以在这里修改相机的前后镜头 是否开启闪光灯等
[self presentViewController:imagePickerController animated:YES completion:nil];

同时,实现UIImagePickerDelegate中的如下方法:

1
2
3
4
5
- (void)imagePickerController:(UIImagePickerController *)picker didFinishPickingMediaWithInfo:(NSDictionary<NSString *,id> *)info {
UIImage * originImage = info[UIImagePickerControllerOriginalImage];//这样获取的是原图像
UIImage * editedImage = info[UIImagePickerControllerEditedImage];//这样获取的是修改后的图像
//...在这里实现图像的保存
}

如果头像的来源为相册,则只需修改imagePickerController的sourceType属性即可:

`imagePickerController.sourceType = UIImagePickerControllerSourceTypePhotoLibrary;`

这样做就可以实现我们的需求了,但是这个方法的缺点也很明显,在这个方法中,我们使用的是系统封装好的UI,参考手机版QQ的选择头像我们可以发现,我们不能自定义相册中图片的分类、排版。同样的,我们也不能自定义编辑头像的界面,你不能将正方形的头像选框改成圆形的。因此,我们需要自己实现一个“UIImagePickerController”。在这个UIImagePickerController中,除了图片来源为拍照的情况下我们采用系统原生的UIImagePickerController以外,编辑图片和从相册中选取图片的功能我们都自己实现。

- PhotoKit和UICollectionView


参考博客:iOS 开发之照片框架详解

对于从相册选择图片的功能,我们可以采用PhotoKit来获取到图片的信息,并通过UICollectionView加以展示,这里主要给出PhotoKit的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#import <Photos/Photos.h>

PHFetchOptions *options = [[PHFetchOptions alloc]init];
options.sortDescriptors = @[[NSSortDescriptor sortDescriptorWithKey:@"creationDate" ascending:YES]];
PHFetchResult * results = [PHAsset fetchAssetsWithOptions:options];
//...这样就取得了照片库中所有照片并将它们通过创建时间排序 当然这只是最简单的做法 还可以创建多个不同类别的相册

//...然后我们要通过如下的代码取得照片
PHImageRequestOptions *requestOptions = [[PHImageRequestOptions alloc]init];
requestOptions.resizeMode = PHImageRequestOptionsResizeModeExact;//这里指定了照片的清晰度
[[PHImageManager defaultManager]requestImageForAsset:results[number]
targetSize:CGSizeMake(length, length)//指定了照片的大小
contentMode:PHImageContentModeDefault
options:requestOptions resultHandler:^(UIImage * result, NSDictionary * info) {
//...在这里展示照片
}];

- 自定义编辑头像的界面


主要有两个方面

  • 展示图片 我采用的方法是向一个UIScrollView中添加一个UIImageView
  • 圆形选框 采用了两个CAShapeLayer,一个是选框的Layer,另一个是遮罩的Layer

实现展示图片的功能首先需要了解UIScrollView中frame,contentSize和contentOffset的区别。同时,为了将图片限制在我们所画的边框内,关键是设置合理的minimumZoomScale(最小缩放比例)以及实时更新ContentSize,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
- (void)imageConfiguration {
self.imageView.frame = CGRectMake(WIDTH/2-LENGTH/2, HEIGHT/2-LENGTH/2-32, _imageSize.width, _imageSize.height);
//设置图片的位置
CGFloat zoomScale =[self zoomScaleWithSize:_imageSize];
//计算初始的zoomScale
CGFloat minimumZoomScale = [self minimumZoomScaleWithSize:_imageSize];
//计算最小的zoomScale
CGFloat maximumZoomScale = (minimumZoomScale <= 1.2) ? 1.2 : minimumZoomScale;
//这里的1.2可以替换成其他值
self.scrollView.minimumZoomScale = minimumZoomScale;
self.scrollView.maximumZoomScale = maximumZoomScale;
self.scrollView.zoomScale = zoomScale;
self.scrollView.contentSize = CGSizeMake(_imageSize.width*zoomScale+WIDTH-LENGTH, _imageSize.height*zoomScale+HEIGHT-LENGTH-64);
//为了保证将图片限制在边框内初始的ContentSize
self.scrollView.contentOffset = CGPointMake(WIDTH/2-LENGTH/2, HEIGHT/2-LENGTH/2-32);
//WIDTH是屏幕宽度 HEIGHT是屏幕高度 LENGTH是边框变长
}

- (CGFloat)zoomScaleWithSize:(CGSize)size {
CGFloat width = size.width;
CGFloat height = size.height;
CGFloat scale = (CGFloat)width/height;
CGFloat screenScale = (CGFloat)WIDTH/HEIGHT;
if (scale > screenScale) {
if ((CGFloat)WIDTH/width*height>LENGTH) {
return ((CGFloat)WIDTH / width);
} else {
return (LENGTH/height);
}
} else {
if ((CGFloat)HEIGHT/height*width>LENGTH) {
return ((CGFloat)HEIGHT/height);
} else {
return (LENGTH/width);
}
}
}
//思路是通过比较宽高比确定让图片正好容纳在屏幕内的比例,同时还保证图片能够包括边框

- (CGFloat)minimumZoomScaleWithSize:(CGSize)size {
CGFloat width = size.width;
CGFloat height = size.height;
if ((LENGTH / height)>(LENGTH / width)) {
return (LENGTH / height);
} else {
return (LENGTH / width);
}
}
//只保证图片能够包括边框即可

- (void)scrollViewDidZoom:(UIScrollView *)scrollView {
self.scrollView.contentSize = CGSizeMake(_imageSize.width*self.scrollView.zoomScale+WIDTH-LENGTH, _imageSize.height*self.scrollView.zoomScale+HEIGHT-LENGTH-64);
}
//UIScrollView代理 在缩放时能够正确的更新contentSize

圆形选框则比较简单,用一个CAShapeLayer即可实现,实现阴影遮罩(效果可以参考手机版QQ)则需要另一个CAShapeLayer,这里有一个问题,如果直接把遮罩设在self.view上,将会在页面切换的时候造成动画的不自然,我的解决方法是在self.view上添加一个UIView的实例contentView作为容器,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
self.contentView.layer.mask = self.maskLayer;
[self.contentView.layer insertSublayer:self.borderLayer above:self.imageView.layer];

- (CAShapeLayer *)borderLayer {
if (!_borderLayer) {
//...在此设置边框
}
return _borderLayer;
}

- (CAShapeLayer *)maskLayer {
if (!_maskLayer) {
_maskLayer = [CAShapeLayer layer];
[_maskLayer setFrame:CGRectMake(0, 0, WIDTH, HEIGHT)];
[_maskLayer setBackgroundColor:[UIColor colorWithRed:0 green:0 blue:0 alpha:0.5].CGColor];
//确定阴影的明暗
//...setPath确定无阴影的范围
}
return _maskLayer;
}

问题

- 修改导航栏的高度


1
2
3
4
5
6
7
8
9
10
11
- (void)viewWillAppear:(BOOL)animated {
[super viewWillAppear:animated];
CGRect navRect = self.navigationController.navigationBar.frame;
self.navigationController.navigationBar.frame = CGRectMake(navRect.origin.x, navRect.origin.y, navRect.size.width, 64);
}

- (void)viewWillDisappear:(BOOL)animated {
[super viewWillDisappear:animated];
CGRect navRect = self.navigationController.navigationBar.frame;
self.navigationController.navigationBar.frame = CGRectMake(navRect.origin.x, navRect.origin.y, navRect.size.width, 44);
}

- 调整导航栏中Title和Button的垂直位置


Title:

1
2
3
4
5
6
7
8
9
10
- (void)viewWillAppear:(BOOL)animated {
[super viewWillAppear:animated];
[self.navigationController.navigationBar setTitleVerticalPositionAdjustment:-10.0 forBarMetrics:UIBarMetricsDefault];
//-10.0可以根据需要调节
}

- (void)viewWillDisappear:(BOOL)animated {
[super viewWillDisappear:animated];
[self.navigationController.navigationBar setTitleVerticalPositionAdjustment:0.0 forBarMetrics:UIBarMetricsDefault];
}

Button:

1
2
[self.barButtonItem setBackgroundVerticalPositionAdjustment:-10.0 forBarMetrics:UIBarMetricsDefault];
//-10.0可以根据需要调节

- 隐藏状态栏


1
2
3
- (BOOL)prefersStatusBarHidden {
return YES;
}

- UIScrollView不能缩放


需要实现代理方法- (UIView *)viewForZoomingInScrollView:(UIScrollView *)scrollView指定需要缩放的子控件

- 截取缩放过的UIImageView中的特定位置和大小的图片


1
2
3
4
5
6
7
8
9
10
- (UIImage *)imageWithZoomScale:(CGFloat)zoomScale {
UIGraphicsBeginImageContextWithOptions(self.imageView.bounds.size, NO, zoomScale);
[self.imageView drawViewHierarchyInRect:self.imageView.bounds afterScreenUpdates:YES];
UIImage * image = UIGraphicsGetImageFromCurrentImageContext();
UIGraphicsEndImageContext();
CGRect imageRect = //...在这里指定位置和大小
CGImageRef sourceImageRef = [image CGImage];
CGImageRef targetImageRef = CGImageCreateWithImageInRect(sourceImageRef, imageRect);
return [UIImage imageWithCGImage:targetImageRef];
}

评论和共享

C语言复习问题总结

发布在 C语言

C语言复习问题总结


1.字段结构的成员的地址

改错题:

1
2
3
4
struct _half_byte {
unsigned short hb0: 4, hb1: 4, hb2: 4, hb3: 4;
} m;
scanf("%hu %hu %hu %hu", &m.hb0, &m.hb1, &m.hb2, &m.hb3);

这里需要注意到字段结构的成员是没有地址的,因此scanf("%hu %hu %hu %hu", &m.hb0, &m.hb1, &m.hb2, &m.hb3);是错误的,正确的代码可以类似:

1
2
3
unsigned short tmp[4];
scanf(“%hu %hu %hu %hu”, &tmp[0] , &tmp[1] , &tmp[2] , &tmp[3]);
m.hb0 = tmp[0], m.hb1 = tmp[1] , m.hb2 = tmp[2] , m.hb3 = tmp[3];

2.&&和||的编译器优化

如果开启了编译器优化,那么若&&的第一个条件为假或者||的第一个条件为真,那么编译器将不会去看&&或||的第二个条件,因此:

Declare int x = 0, y = 1; , which values of the following expressions are nonzero?

A. x++ + y--

B. y-x||x++, x

C. x*y&&y--, y

D. y-- ? y++ : y

这道题目的B和C为例,B中y-x已经为1,所以编译器将忽略x++,所以x仍然为0,所以B错误。而C中x*y为0所以编译器将忽略y–,所以y为1,C正确。

3.注意标识符和关键字的区别

例如:main是一个合法的标识符,而非关键字。

再例如:Case是一个合法的标识符,而非关键字。(注意C语言区分大小写)

4.词法分析

How many tokens are there in the statement of *p+++=12.L;?

A. 5

B. 6

C. 7

D. 10

记号共有5类:标识符、关键字、常量(含字符串常量)、运算符、标点符号。

*p+++=12.L;可以被分解为 * p ++ += 12.L ;共计6个记号,所以,答案为B。

5.转义序列

根据文档:

Escape sequences are used to represent certain special characters within string literals and character constants.

在C中可以由 \(反斜杠)+ 字符来进行转义。

6.类型转换

long x, y; x = -6L; y = 5UL; Which expression is equal to 1?

A. x<y && -6L<5UL

B. x<y && -6L>5UL

C. x>y && -6L<5UL

D. x>y && -6L>5UL

x,y的类型为long,因此5UL将会被转换为5L,所以x<y。而在进行比较运算的时候-6L会被提升至Unsigned Long,此时-6L>5UL,所以答案选B。

7.后缀自增自减运算符的计算延迟

后缀式++/–在遇到&& || ?: , 运算符后、或者完整表达式结束后自增/自减。

8.注意作用域、链接和存储时期

作用域描述程序中可以访问一个标识符的一个或多个区域;链接包括外部、内部和空链接,具有空链接的变量被代码块或函数原型所私有,外部链接的变量可以在多文件程序的任何地方使用,内部链接的变量可以在一个文件的任何地方使用;静态存储时期的变量将在程序执行期间一直存在,并且只能初始化一次。

具体可以参考C Primer Plus第十二章《存储类、链接和内存管理》或是课本。以下列出5个存储类的组合(来自C Primer Plus):
















































存储类 时期 作用域 链接 声明方式
自动 自动 代码块 代码块内
寄存器 自动 代码块 代码块内,使用关键字register
具有外部链接的静态 静态 文件 外部 所有函数之外
具有内部链接的静态 静态 文件 内部 所有函数之外,使用关键字static
空链接的静态 静态 代码块 代码块内,使用关键字static

In the following descriptions about the using of static, which ones are correct?

A. The static declaration can be used to variables and functions.

B. The external static declaration limits the scope of that object.

C. Internal static variables are local to a particular function just as auto variables are.

D. Internal static variables provide permanent storage and are initialized only once.

A正确,B external static具有内部链接,因此被限制了只能被当前文件引用,正确,C内部定义的静态变量具有代码块作用域,正确,D正确。

同时在另外一个文件中引用具有外部链接的变量时需要使用关键字 extern,因此,下面一道题选D。

Suppose that file_a.c and file_b.c can be compiled independently. and they share the following global variables

extern int x; char ch;

which are declared in file_a.c. The allowed global variables declared in file_b.c are

A、extern int x; char ch;

B、extern int x; extern char ch;

C、int x; char ch;

D、int x; extern char ch;

9.改错题注意悬挂指针

例如:

1
2
3
4
char *a[5];
int i = 0;
for (i=0; i<5; i++)
scanf("%s", a[i]);

10.Switch中的break

若switch中的case不加break,将会将该case后的所有语句全部执行完。

11.字段成员的内存分配

字段成员的内存分配是由低位到高位的。例如下面的题目,答案为C:

Suppose declared:

1
2
3
4
5
6
7
struct direction {
unsigned short int east:4,south:4,west:4,north:4; //east为最低位4,north为最高位1
};
union ud{
unsigned short int all;
struct direction d;
} a={0x1234};

the output of printf("%d\n",a.d.south); is

A、1

B、2

C、3

D、4

12.细心审题

C语言考试审题还是很重要的,稍微一不小心看错了一个字母,有可能题目就错了,务必仔细审题。

评论和共享

iOS学习笔记(二)

发布在 iOS开发

因为一些原因,用了整整一周的时间来重构项目,因为期末考试的原因,决定暑假继续这个项目,在复习之前最后总结一下这一段开发过程中遇到的一些问题。

定位问题


参考博客:后台定位上传的代码实践|里脊串的开发随笔

需求是每隔一定时间向服务器上传一次地理位置,而不管用户或系统是否杀死了APP。这里参考了里脊串博客里的写法,使用BackgroundMode中的Location updates即可实现。但是与这篇博客中的APP的需求不同,并不需要考虑速度距离等因素,只要考虑时间即可,因此可以通过判断两次location中的时间戳间隔即可。

1
2
3
4
5
#define kUpdateTimeInteval 60.0 //上传间隔
@interface LocationManager()
@property (nonatomic, strong) CLLocation * lastLocation; //最新一次的地理位置
@property (nonatomic) double timeInteval; //上一次上传地理位置时的时间戳
@end

然后在locationManager的委托方法中加入如下代码:

1
2
3
4
5
6
7
8
- (void)locationManager:(CLLocationManager *)manager didUpdateLocations:(NSArray<CLLocation *> *)locations {
_lastLocation = locations[0];
if (_lastLocation.timestamp.timeIntervalSince1970 - _timeInteval > kUpdateTimeInteval) {
NSLog(@"update location");
[self updateLocation]; //上传地理位置
_timeInteval = _lastLocation.timestamp.timeIntervalSince1970;
}
}

需要注意的是,在进入后台模式或者是APP被杀的情况下,如果设备的位置没有发生变化,那么locationManager的 didUpdateLocations方法将不会被调用,因此尽管间隔的时间已经超过了设定的时间,地理位置也不会被上传。

不显示动画


由于APP中存在用户注册和登录的需求,因此需要加入验证码认证,两次验证码之间应有一分钟的间隔,此时,UI应该每隔1s刷新一次剩余时间以提醒用户,因此我使用了一个每隔1s执行一次的NSTimer去刷新UI,却发现每次刷新的时候按钮上的Title都会有渐入渐出的动画效果。后来发现这是UIButtonTypeRoundedRect的自带动画效果,为了不让这个渐变动画干扰了UI的刷新,加入如下代码:

1
2
3
4
[UIView performWithoutAnimation:^{
//在这里设置UIButton的属性如Text等
[_button.layer layoutIfNeeded];
}];

自定义UIBarButtonItem


参考了StackOverFlow

需求是自定义一个同时带图片和文字的UIBarButtonItem,查阅文档和搜索后发现UIBarButtonItem有以下的方法:

- (instancetype)initWithCustomView:(UIView *)customView;

因此我们可以先实例化一个UIButton,给这个UIButton添加Image并且设置Title,再用这个UIButton去实例化一个UIBarButtonItem即可,代码如下:

1
2
3
4
5
6
7
8
UIButton * button = [UIButton buttonWithType:UIButtonTypeRoundedRect];
[button setTitle:@"返回" forState:UIControlStateNormal];
button.titleLabel.font = [UIFont systemFontOfSize:17.0];
[button setImage:[UIImage imageNamed:@"back"] forState:UIControlStateNormal];
button.imageEdgeInsets = UIEdgeInsetsMake(0, -3, 0, 0); //使用这个属性控制UIImageView和UILabel之间的距离
[button sizeToFit]; //设定button的frame
[button addTarget:self action:@selector(back) forControlEvents:UIControlEventTouchUpInside];
UIBarButtonItem * leftButton = [[UIBarButtonItem alloc]initWithCustomView:button];

但是这样又发现一个新的问题,我们无法控制UIBarButtonItem的边距。官方文档UINavigationItem中对于leftBarButtonItems和rightBarButtonItems这两个属性中有如下描述:

leftBarButtonItems are placed in the navigation bar left to right with the first item in the list at the left outside edge and left aligned.

rightBarButtonItems are placed right to left with the first item in the list at the right outside edge and right aligned.

因此我们可以再实例化一个UIBarButtonItem并设置它的width,完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
UIBarButtonItem * negativeSpacer = [[UIBarButtonItem alloc]initWithBarButtonSystemItem:UIBarButtonSystemItemFixedSpace target:nil action:nil];
negativeSpacer.width = -16.0; //可根据实际需要调整
UIButton * button = [UIButton buttonWithType:UIButtonTypeRoundedRect];
[button setTitle:@"返回" forState:UIControlStateNormal];
button.titleLabel.font = [UIFont systemFontOfSize:17.0];
[button setImage:[UIImage imageNamed:@"back"] forState:UIControlStateNormal];
button.imageEdgeInsets = UIEdgeInsetsMake(0, -3, 0, 0);
[button sizeToFit];
[button addTarget:self action:@selector(back) forControlEvents:UIControlEventTouchUpInside];
UIBarButtonItem * leftButton = [[UIBarButtonItem alloc]initWithCustomView:button];
self.navigationItem.leftBarButtonItems = @[negativeSpacer, leftbutton];

去除UINavigationBar的阴影


我采用的是如下的方法:

[nav.navigationBar setShadowImage:[[UIImage alloc]init]];

评论和共享

C语言第四次作业

发布在 C语言

第一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>;
void swap(int *a, int *b);
int main (void)
{
int number[10];
int i, j;//循环变量
while (scanf("%d", &amp;number[0]) != EOF)
{
for (i = 1 ; i &lt; 10 ; i++)
scanf("%d", &amp;number[i]);
for (i = 0 ; i &lt; 9 ; i++)
{
for (j = 0 ; j &lt;= 8 - i ; j++)
{
if (number[j] &gt; number[j+1])
swap(&amp;number[j], &amp;number[j+1]);
}
}
for (i = 0 ; i &lt; 10 ; i++)
{
if (i != 0) printf("-&gt;");
printf("%d", number[i]);
}
putchar('\n');
}
return 0;
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
return;
}

第二题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>;
int main (void)
{
long number;
char currentByte;
int count;
while (scanf("%ld", &amp;number) != EOF)
{
for (count = 7 ; count &gt;= 0 ; count--)
{
currentByte = (((0xf &lt;&lt; (count * 4)) &amp; number) &gt;&gt; (count * 4)) &amp; 0xf;
printf("%hd(%c) ", currentByte, currentByte);
}
putchar('\n');
}
return 0;
}

第三题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>;
void swapArray(int a[], int n);
void swap(int *a, int *b);
int main (void)
{
int number[100];
int totalNumber, individualNumber;
int count, i;//循环变量
scanf("%d", &amp;totalNumber);
for (count = 0 ; count &lt; totalNumber; count++)
{
scanf("%d", &amp;individualNumber);
for (i = 0 ; i &lt; individualNumber ; i++)
scanf("%d", &amp;number[i]);
swapArray(number, individualNumber);
for (i = 0 ; i &lt; individualNumber ; i++)
{
if (i != 0) putchar(' ');
printf("%d", number[i]);
}
putchar('\n');
}
return 0;
}
void swapArray(int a[], int n)
{
int startIndex = 0;
int endIndex = n - 1;
while (startIndex &lt;= endIndex)
{
swap(&amp;a[startIndex], &amp;a[endIndex]);
startIndex++;
endIndex--;
}
return;
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
return;
}

第四题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>;
void swap(int *a, int *b);
void moveArray(int a[], int n, int m);//轮移数组,其中n为总个数,m为轮移次数
int main (void)
{
int number[22];
int individualNumber, middleNumber;
int i;//循环变量
while ((scanf("%d", &amp;individualNumber), individualNumber) != 0)
{
scanf("%d", &amp;middleNumber);
for (i = 0 ; i &lt; individualNumber ; i++)
scanf("%d", &amp;number[i]);
moveArray(number, individualNumber, middleNumber);
for (i = 0 ; i &lt; individualNumber ; i++)
{
if (i != 0) putchar(' ');
printf("%d", number[i]);
}
putchar('\n');
}
return 0;
}
void moveArray(int a[], int n, int m)
{
if (m == 0)
{
return;
}
else
{
int temp, count;
temp = a[0];
for (count = 0 ; count &lt; n - 1 ; count++)
a[count] = a[count+1];
a[n-1] = temp;
moveArray(a, n, --m);
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
return;
}

评论和共享

iOS学习笔记(一)

发布在 iOS开发

最近开始了自己的第一个项目,到目前为止已经写完了基本的界面,将开发过程中遇到的一些问题列举如下:

自定义cell分割线

首先设置 tableView.separatorStyle = UITableViewCellSeparatorStyleNone;

然后在自定义的cell的实现文件内实现如下的方法

1
2
3
4
5
6
7
8
9
10
11
12
- (void)drawSeparator{
_separatorlineLayer = [CAShapeLayer layer];
CGMutablePathRef separatorShapePath = CGPathCreateMutable();
[_separatorLayer setFillColor:[UIColor clearColor].CGColor];
[_separatorLayer setStrokeColor:[UIColor headlineColor].CGColor];
_separatorLayer.lineWidth = 0.5f;
CGPathMoveToPoint(separatorShapePath, NULL, 0.0f, 0.0f);
CGPathAddLineToPoint(separatorShapePath, NULL, WIDTH, 0.0f);
[_headlineLayer setPath:separatorShapePath];
CGPathRelease(separatorShapePath);
[self.contentView.layer addSublayer:_separatorLineLayer];
}

其中,_separatorLayerCAShapeLayer的实例,setStrokeColor方法设定了线的颜色,CGPathMoveToPointCGPathAddLineToPoint设定了线的起始点。

同理,可以类似地实现画点或者更为复杂形状的效果。

iOS8之后cell的动态高度计算

首先使用autolayout布局,且确保cell的contentView至少top和bottom都和cell内部的View建立了约束。之后添加如下代码

1
2
tableView.estimatedRowHeight = 60.0f;
tableView.rowHeight = UITableViewAutomaticDimension;

需要注意的是,必须要为tebleView的estimiatedRowHeight属性设定值。

返回键盘的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- (void)viewDidLoad{
[super viewDidLoad];
//注册通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(keyboardWillShow:) name:UIKeyboardWillShowNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(keyboardWillHide:) name:UIKeyboardWillHideNotification object:nil];
}

- (void)dealloc {
//移除通知
[[NSNotificationCenter defaultCenter]removeObserver:self];
}

- (void)keyboardWillShow:(NSNotification *)notification{
//键盘弹出时调用
NSDictionary * userInfo = [notification userInfo];
NSValue * frameValue = [userInfo objectForKey:UIKeyboardFrameEndUserInfoKey];
CGRect keyboardRect = [frameValue CGRectValue];
NSInteger height = keyboardRect.size.height;
}

- (void)keyboardWillHide:(NSNotification *)notification{
//键盘隐藏时调用
}

height中储存的即为当前键盘的高度

小心block导致的retain cycle

如果在block中需要访问本类的实例变量,需要使用

__weak UIViewController * weakSelf = self;

self持有了block,而block通过捕获self来访问实例变量,导致保留换的产生,通过__weak打破保留环。

评论和共享

C语言第三次作业

发布在 C语言

第一题 C语言成绩


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<string.h>
void swap(int *score_a, int *score_b, char *name_a, char *name_b);
int main (void)
{
int number, count;
while (scanf("%d", &number) != EOF)
{
putchar('\n');
int scores[number];
char names[number][81];
for (count = 0 ; count < number ; ++count)
scanf("%s%d", names[count], &scores[count]);
int i, j;
for (i = 0 ; i < number ; ++i)
for (j = i ; j < number ; ++j)
if (scores[i] < scores[j])
swap(&scores[i], &scores[j], &names[i][0], &names[j][0]);
for (count = 0 ; count < number ; ++count)
printf("%s %d\n", names[count], scores[count]);
putchar('\n');
}
return 0;
}

void swap(int *score_a, int *score_b, char *name_a, char *name_b)
{
int t;
char str_t[81];
t = *score_a;
*score_a = *score_b;
*score_b = t;
strcpy(str_t, name_a);
strcpy(name_a, name_b);
strcpy(name_b, str_t);
return;
}

第二题 冒泡排序


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
int main(void)
{
int sequence[10];
int count;
int i, j;
int temp;
while (scanf("%d", &sequence[0]) != EOF)
{
for (count = 1 ; count < 10 ; ++count)
scanf("%d", &sequence[count]);
for (i = 0 ; i < 10 ; ++i)
{
for (j = 0 ; j < 8 - i ; ++j)
{
if (sequence[j] > sequence[j+1])
{
temp = sequence[j];
sequence[j] = sequence[j+1];
sequence[j+1] = temp;
}
}
}
for(count = 0 ; count < 10 ; ++count)
printf("%d ", sequence[count]);
putchar('\n');
}
return 0;
}

第三题 n人报数(此题可查找“约瑟夫问题”)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
int main (void)
{
int number,count;
int current;
int i;
while (scanf("%d", &number) != EOF)
{
int people[10000];
for (i = 0 ; i < number ; ++i)
people[i] = 1;
count = number;
current = 0;
i = 0;
while (count > 1)
{
if (i >= number)
i = 0;
if (people[i] == 1)
current += 1;
if (count == 1)
break;
if (current == 3)
{
people[i] = 0;
count -= 1;
current = 0;
}
i++;
}
for (i = 0 ; i < number ; ++i)
if (people[i] == 1)
{
printf("%d\n", i + 1);
break;
}
}
return 0;
}

第四题 定义宏交换参数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#define Swap(x,y) {x = x + y; y = x - y; x = x - y;}

int main (void)
{
int a, b;
int count = 0;
while (scanf("%d%d", &a, &b) != EOF)
{
if (count)
putchar('\n');
count += 1;
printf("Case %d:\n", count);
printf("Before Swap:a=%d b=%d\n", a, b);
Swap(a,b);
printf("After Swap:a=%d b=%d\n", a, b);

}
return 0;
}

第五题 字符串复制


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
void mycpy (char s[], char t[], int n);
int main (void)
{
int number;
char sentence[1001];
char result[1001];
int n;
scanf("%d", &number);
getchar();//读取\n
int count;
for (count = 0 ; count < number ; ++count)
{
fgets(sentence, 1001, stdin);
scanf("%d", &n);
getchar();//读取\n
mycpy(result, sentence, n);
printf("%s\n", result);
}
return 0;
}
void mycpy (char s[], char t[], int n)
{
int i;
for (i = 0 ; i < n ; ++i)
{
s[i] = t[i];
}
s[n] = '\0';
return;
}

第六题 统计


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
int main (void)
{
char currentChar;
int numberCount[10] = {0};
int englishCharCount = 0;
int otherCount = 0;
int count;
while ((currentChar = getchar()) != EOF)
{
switch (currentChar)
{
case '0': numberCount[0] += 1 ; break;
case '1': numberCount[1] += 1 ; break;
case '2': numberCount[2] += 1 ; break;
case '3': numberCount[3] += 1 ; break;
case '4': numberCount[4] += 1 ; break;
case '5': numberCount[5] += 1 ; break;
case '6': numberCount[6] += 1 ; break;
case '7': numberCount[7] += 1 ; break;
case '8': numberCount[8] += 1 ; break;
case '9': numberCount[9] += 1 ; break;
default: break;
}
if ((currentChar >= 'A' && currentChar <= 'Z') || (currentChar >= 'a' && currentChar <= 'z'))
englishCharCount += 1;
else if (!(currentChar >= '0' && currentChar <= '9'))
otherCount += 1;
}
for (count = 0 ; count < 10 ; ++count)
printf("Number %d: %d\n", count, numberCount[count]);
printf("characters: %d\n", englishCharCount);
printf("other: %d\n", otherCount);
return 0;
}

第七题 选择排序


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
int main (void)
{
int sequence[20];
int number;
int count;
int i, j;
int temp;
while (scanf("%d", &number), number != 0)
{
for (count = 0 ; count < number ; ++count)
scanf("%d", &sequence[count]);
for (i = 0 ; i < number ; ++i)
for (j = i ; j < number ; ++j)
if (sequence[i] > sequence[j])
{
temp = sequence[i];
sequence[i] = sequence[j];
sequence[j] = temp;
}
for (count = 0 ; count < number ; ++count)
{
if (count)
putchar(' ');
printf("%d", sequence[count]);
}
putchar('\n');
}
return 0;
}

评论和共享

C语言第二次作业

发布在 C语言

1、哥德巴赫猜想(2)——改编自习题5.14


题目描述:

哥德巴赫作了如下猜想:一个大于等于4的偶数都是两个素数之和。编写一个程序证明对于在正整数Begin、End之间的偶数,这一猜测成立。将判断一个数是否是素数定义成函数。
本题包含多组测试数据。

输入格式说明:

每组测试数据输入占一行,包括两个正整数,依次为Begin,End,4≤Begin<End≤200,遇文件尾测试结束。

输出格式说明:

输出在规定范围内所有偶数的哥德巴赫猜想形式的分解,存在多种不同输出结果组合时,输出满足要求的结果中分解后第一个数最小的结果,需要在第i组测试数据结果输出前添加一行提示信息:“CASE:i”,表示是第i组测试数据对应的结果,相邻两组测试样例的输出结果之间空一行。

样例输入:

10 20
45 145

样例输出:

CASE:1
COLDBACH’S CONJECTURE:
Every even number n>=4 among 10~20 is the sum of two primes:
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17

CASE:2
COLDBACH’S CONJECTURE:
Every even number n>=4 among 45~145 is the sum of two primes:
46=3+43
48=5+43
50=3+47
52=5+47
54=7+47
56=3+53
58=5+53
60=7+53
62=3+59
64=3+61
66=5+61
68=7+61
70=3+67
72=5+67
74=3+71
76=3+73
78=5+73
80=7+73
82=3+79
84=5+79
86=3+83
88=5+83
90=7+83
92=3+89
94=5+89
96=7+89
98=19+79
100=3+97
102=5+97
104=3+101
106=3+103
108=5+103
110=3+107
112=3+109
114=5+109
116=3+113
118=5+113
120=7+113
122=13+109
124=11+113
126=13+113
128=19+109
130=3+127
132=5+127
134=3+131
136=5+131
138=7+131
140=3+137
142=3+139
144=5+139

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <math.h>

int isPrime (int x);
int main (void)
{
int begin, end;
int count, number;
int subnumber1, subnumber2;
for (count = 1 ; scanf("%d%d", &begin, &end) != EOF ; ++count)
{
if (count != 1)
putchar('\n');
printf("CASE:%d\n", count);
printf("COLDBACH'S CONJECTURE:\n");
printf("Every even number n>=4 among %d~%d is the sum of two primes:\n", begin, end);
if (begin % 2 != 0)
begin++;
for (number = begin ; number <= end ; number += 2)
{
for (subnumber1 = 2 ; subnumber1 <= (number/ 2) ; ++subnumber1)
{
subnumber2 = number - subnumber1;
if (isPrime(subnumber2) && isPrime(subnumber1))
{
printf("%d=%d+%d\n", number, subnumber1, subnumber2);
break;
}
}
}
}
return 0;
}

/*************************************************
Function: isPrime
Description: 判断正整数是否为素数
Input: 一个正整数x
Return: 1表示素数 0表示合数
*************************************************/
int isPrime (int x)
{
int i;
for (i = 2 ; i <= sqrt(x) ; ++i)
if (x % i == 0) return 0;
return 1;
}

2、第k个数——改编自习题5.13


题目描述:

输入正整数n和k,输出n中从右端开始的第k个数字的值(k从1开始)。将求n中右端第k个数字定义成函数,如果k超过了n的位数,则函数返回-1;否则返回n中第k个数字。
本题包含多组测试数据。

输入格式说明:

每组测试数据输入占一行,包括两个正整数,依次为n,k,n在1~4000000000之间(闭区间),遇文件尾测试结束。

输出格式说明:

每组测试样例的输出结果占一行,输出函数返回结果。

样例输入:

321 3
421 4
42 12

样例输出:

3
-1
-1

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
int getKFromN (unsigned long n , int k);

int main (void)
{
unsigned long n;
int k;
while (scanf("%lu%d", &n, &k) != EOF)
{
printf("%d\n", getKFromN(n, k));
}
return 0;
}

/*************************************************
Function: getKFromN
Description: 返回n中从右端开始的第k个值
Input: 一个1~4000000000的正整数n 一个正整数k
Return: 一个正整数 n中的第k个数字 -1表示越位
*************************************************/
int getKFromN (unsigned long n , int k)
{
int unit = 0;//表示最后一位
int count;//表示当前位数
unsigned long result = n;//存储结果
for (count = 1 ; count <= k ; count++)
{
unit = result % 10;
result = result / 10;
}
if (!(unit == 0 && result == 0))
return unit;
else
return -1;
}
```

## 3、冰雹数——改编自习题5.11

* * *

### 题目描述:

n(0)是一个给定的正整数,对于i=0,1,2,...,定义:(1)若n(i)是偶数,则n(i+1)=n(i)/2;(2)若n(i)是奇数,则n(i+1)=3n(i)+1;(3)若n(i)是1,则序列结束。
本题包含多组测试数据。


### 输入格式说明:

每组测试数据输入占一行,包括一个正整数n0,n0在1~4000000000之间(闭区间),遇文件尾测试结束。

### 输出格式说明:

输出冰雹数序列以及序列数的总个数,相邻两组测试样例的输出结果之间空一行。

### 样例输入:

77
92


### 样例输出:

Hailstone generated by 77:
77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Number of hailstone generated:23

Hailstone generated by 92:
92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Number of hailstone generated:18

### 解答:

#include <stdio.h>
unsigned long long getNextHailstoneNumber (unsigned long long n);

int main (void)
{
unsigned long long number;
int count;
int flag = 1;
while (scanf(“%llu”, &number) != EOF)
{
if (!flag)
putchar(‘\n’);
printf(“Hailstone generated by %llu:\n”, number);
count = 0;
while (number != 1)
{
count += 1;
printf(“%llu “, number);
number = getNextHailstoneNumber(number);
}
printf(“1\n”);
printf(“Number of hailstone generated:%d\n”, count + 1);
flag = 0;
}
return 0;
}

/*
Function: getNextHailstoneNumber
Description: 返回以n为起始数的下一个冰雹数
Input: 一个的正整数n
Return: 一个正整数,表明n的下一个冰雹数
*/

unsigned long long getNextHailstoneNumber (unsigned long long n)
{
if (n % 2 == 0)
return n / 2;
else
return 3 * n + 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

## 4、计算题——改编自习题5.10

* * *

### 题目描述:

编程计算s=1+1/2!+1/3!+1/4!+...+1/n!。n由终端输入,将计算n!定义成函数。
本题包含多组测试数据。

### 输入格式说明:

每组测试数据输入占一行,包括一个正整数n,n在1~20之间(闭区间),遇文件尾测试结束。

### 输出格式说明:

每组测试样例的输出结果占一行,输出s,保留18位小数。
注:20!=2432902008176640000。

### 样例输入:

1
2

### 样例输出:

1.000000000000000000
1.500000000000000000

### 解答:

#include <stdio.h>
long long getFactorial (int n);

int main (void)
{
int number;
int i;//循环变量
double s;
while (scanf(“%d”, &number) != EOF)
{
s = 0;
for (i = 1 ; i <= number ; ++i)
{
s += 1.0 / getFactorial(i);
}
printf(“%.18f\n”, s);
}
return 0;
}

/*
Function: getFactorial
Description: 返回n的阶乘
Input: 一个正整数n
Return: 一个正整数n!
*/
long long getFactorial (int n)
{
int count;
long long result = 1;
for (count = 2 ; count <= n; ++count)
{
result *= count;
}
return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

## 5、掷骰子游戏——改编自习题5.1

* * *

### 题目描述:

编写一个模拟“投掷双骰子”的游戏程序。游戏规则:每轮投两次,取两次的和,第一轮若和为7或11则获胜,游戏结束;若和为2,3,或12则输了,失败结束;若和为其他数字,则将此值作为自己的点数,继续第二轮,第三轮⋯⋯直到某轮的和等于该点数则获胜,若出现和为7,则输掉游戏。模拟每掷一次骰子的随机取数规则:输入一个非负整数,称为启动数,你需要计算得到启动数各位数之和记为sum,现将1~6这6张数字卡片按顺时钟方向摆放一个环,一只蚂蚁每次从数字为1的卡片摆放的位置出发,这时你告诉蚂蚁按顺时钟方向走sum步,蚂蚁最终停留位置上的卡片数字即视为本次掷骰子得到的点数。
本题包含多组测试数据。


### 输入格式说明:

第一行输入n表示测试样例的个数,后面紧接着有n行输入,每行输入包含两个非负整数记为a,b,整数范围在0~10000之间(闭区间),视为第一轮两次投掷的启动数,若进行到了第n轮时,则第n轮两次投掷的启动数分别看作是a+n-1,b+n-1;


### 输出格式说明:

每组测试样例的输出结果占一行,输出本次游戏的最终结果。

### 样例输入:

3
1234 1
1 42
0 422

### 样例输出:

success!
fail!
success!

### 解答:

#include <stdio.h>
int calcSum (int startNumber);

int main (void)
{
int number;
int count;
int a, b;
int dieA, dieB, dieSum;
int winNumber;
int n;
scanf(“%d”, &number);
for (count = 0 ; count < number ; ++count)
{
scanf(“%d%d”, &a, &b);
dieA = calcSum(a) % 6 + 1;
dieB = calcSum(b) % 6 + 1;
dieSum = dieA + dieB;
if (dieSum == 7 || dieSum == 11)
{
printf(“success!\n”);
continue;
} else if (dieSum == 2 || dieSum == 3 || dieSum == 12)
{
printf(“fail!\n”);
continue;
} else
{
winNumber = dieSum;
}
n = 1;//此处与题目描述不符
do
{
dieA = calcSum(a + n) % 6 + 1;
dieB = calcSum(b + n) % 6 + 1;
dieSum = dieA + dieB;
n += 1;
if (dieSum == 7)
{
printf(“fail!\n”);
break;
}
}while (dieSum != winNumber);
if (dieSum == winNumber)
printf(“success!\n”);
}

return 0;

}

/*
Function: calcSum
Description: 计算启动数的各位的和sum
Input: 一个正整数n(启动数)
Return: 一个正整数n(启动数各个位数的和)
*/
int calcSum (int startNumber)
{
int unit = 0;
int result = startNumber;
int sum = 0;
while (result != 0)
{
unit = result % 10;
sum += unit;
result = result / 10;
}
return sum;
}
`

评论和共享

作者的图片

码龙黑曜

iOS开发者/计算机科学/兽人控


华中科技大学 本科在读


Wuhan, China