EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない　それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜，即便如此我也要前进，因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

我的算法天梯之路之-最大子阵列

- -

我的算法天梯之路之-最大子阵列

在一个数组中找出和最大的连续几个数。（至少包含一个数）
例如：
数组A[] = [−2, 1, −3, 4, −1, 2, 1, −5, 4]，则连续的子序列[4,−1,2,1]有最大的和6.
输入格式
第一行输入一个不超过1000的整数n。
第二行输入n个整数A[i]。
输出格式
第一行输出一个整数，表示最大的和。

样例输入

3
1 1 -2
样例输出
2

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 #include <stdio.h>
 #define N 1001
 int maxsum(int a[],int n){
    int sum = a[0];
    int b = 0;
    for (int i = 0;i < n;i++){
        if(b>=0) b+=a[i]; else b=a[i];
        if(b>sum)
        sum = b;
    }
    return sum;
 }
 int main(){
    int n,a[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);

    printf("%d",maxsum(a,n));
    return 0;
 }

(转)Linux on Android——在Android手机上跑Linux教程

- -

(转)Linux On Android——在Android手机上跑Linux教程(以Ubuntu14.04-core为例）

前言

Android 是基于 Linux 内核的开源操作系统，主要用在移动设备上。当然同样是基于 Linux 内核的操作系统，现在支持的 Android 的智能手机理论来说都能运行基于 Linux 的操作系统，比如现在流行的发行版：Ubuntu、Fedora 等等。不仅如此，现在的智能移动设备的硬件也越来越强，更为能运行 Linux 系统提供了良好的硬件支持。今天就带大家来尝试一下在 Android 手机上安装 Ubuntu14.04操作系统。 有关说明:

  • 原帖点这里
  • 注:ubuntu14.04-core类似于Ubuntu系列的服务器版本,想使用图形界面的朋友可以在系统安装完成后,自行下载Ubuntu的图形界面(KDE,GNOME,XFCE或LXDE,而在图形界面方面博主较为推荐LXDE,轻便,简捷,占用资源及空间较少.但是用户友好度不高,适合低配低容量手机(装在SD卡的读者可以无视这个建议!))
  • 想用图形界面,但又怕安装图形界面麻烦的读者可以直接安装Ubuntu12.04-Full,更多其他linux发行版可以在sourceforge.net的LinuxonAndroid目录列表中查询,详情可以继续往下阅读.

配置要求

  • 设备需要 root 权限(重点,没有root的手机以下的关键操作基本都无法执行)，并且安装了 BusyBox
  • 最小 1GHz 处理器(推荐)
  • Android 系统版本 2.1 或以上
  • 手机容量,一般有张4GB的SD卡就够了(其他像kali的映像(至少5G)除外) (安装full映像需要3.5GB,small映像需要2G,core映像则只需要1G)
  • 支持 Ext2 文件系统(大部分 Android 设备应该都支持)

博主设备

  • 手机型号:lenvon A5500
  • 处理器主频:1.6GHz
  • 无SD卡(由于博主装的是core版,使用1G的机身空余容量即可)
  • Android版本:5.0

需要的软件(此处清单基本照抄原帖主)

开始安装

0. 取得 ROOT 权限

首先您的手机需要 root，也就是能够获得root权限去操作，相当于越狱。不懂的可以去 Google 一下“Android获取root权限”。root是前提，所以先要把这个做好，不过现在很多ROM都做的很好，比如MIUI就有很好的权限管理。

1. 安装文件下载

首先就是下载必要的文件，这个是在 sourceforge.net 上的一个叫 Linux-on-Android 的项目。 我上面给的地址中有一般三个包可供下载(Ubuntu14.04除外,目前只有core版)：

其实下面就有英文的介绍，我就在这里简单介绍一下：

full 映像包含了完整的 Ubuntu 系统，其中包括 Unity 桌面，还有很多如GIMP等常用软件，非常齐全。需要 3.5G 以上空间。

small 映像包含了的基本的 Ubuntu 系统，其中包括 LXDE 桌面，需要 2G 以上空间。

core 映像包含了基础的 Ubuntu 系统，不过这个没有GUI的，也就是没有桌面只有命令行。

下载完待安装的 Ubuntu 14.04-core 的映像文件，然后我们安装还需要安装脚本，也就是上面说的 ubuntu.sh ，还有安装后的启动脚本 bootscript.sh 。有了这些文件后我们在手机的根目录，新建一个文件夹取名为 ubuntu ，然后把这里我们刚才下载好的文件放到这个文件夹里面，到这里 ubuntu 文件夹里就分别有 ubuntu.img、ubuntu.sh、bootcript.sh 这三个文件了。

注:由于原帖主安装的是Ubuntu12.04,文件系统才用的是ext2,而此处我们要安装的是Ubuntu14.04-core所以两个脚本文件的内容有些许的出入,大家用编辑器将两个.sh文件打开,用搜索替换功能将脚本里面的"ext2"替换成"ext4"保存退出即可.

安装软件(此处照搬原帖,博主懒得码字了…)

首先需要的是 Terminal 这个软件，也就是一个终端，通过终端我们可以用来执行很多命令和脚本。上面我给出了Google Play的地址，这个在很多地方都有的下的，还有Android VNC Viewer也可以在 Google Play 里面找到安装。

在这里我要说一下 BusyBox，它使得你可以在 Terminal 中运行很多命令，现在很多 Android 的 Rom (我用的MIUI_v4_2.8.10也是) 的终端中很多命令都不能运行，比如 cp、mv、cut 等，但是这些都是我们脚本里面需要用到的，如果不能运行这些命令而执行脚本的话，会提示 **: not found 这样的提示。所以安装 BusyBox 可以使得这些命令都能够在终端里面执行。如果你的Rom本来够强大已经包含了BusyBox的新版本，能够运行基本的shell命令的话，那也可以不用装这个。

当然安装 BusyBox 以及后面我们在 Terminal 中都需要 root 权限，如果是MIUI系统的话则可以直接在 授权管理 > ROOT权限管理 里面打开该选项，然后需要root权限的时候允许就可以了。其他的系统我没用过，不过可以直接用 一键ROOT工具 来操作。

安装 BusyBox，安装好后，打开BusyBox点击 Install 开始安装，如果弹出需要ROOT权限，点下一步允许就行!

安装 ubuntu 14.04-core

首先，打开 终端模拟器(Terminal) ，在光标处输入 “cd /ubuntu”(不包括引号，注意cd后有空格)然后回车，这样就来到了刚才我们在SD卡里面新建的目录了.

接下来我们就要开始运行 ubuntu.sh 这个安装脚本了，但在这之前我们需要使用 root 用户来运行这个脚本，在终端中使用命令 “su” 来切换至 root 用户权限，如果弹出授权信息点击下一步允许就行了，或者直接用 一键ROOT 来开启终端重复上面操作，成功后如图之前的“$”变成了“#”，这就说明已经获得Root权限了

然后运行安装脚本，输入命令 “sh ubuntu.sh”，进行安装

然后脚本为你建立了一个名字为“ubuntu”的帐号，这里提示你需要为你的帐号设置一个密码，这个密码会在以后你操作 Ubuntu 的时候一些授权应用到，比如我在这里设置密码为：“ubuntu”，这里注意的是在终端里面输入密码是不会显示出来的，你看见光标没有动静，但实际上你已经输入进去了。回车后提示再次输入密码以保证你两次密码一样

密码设置完成后，提示是否启动VNC服务和SSH服务，我们只要输入“y”然后回车，开启了这两个服务后我们才能通过远程连接来连上系统

然后提示我们输入设备屏幕的尺寸，我的屏幕是1280x800的，所以我输入“1280x800”（小米手机注意：小米手机是854×480的，但是后面用Android VNC 连接的时候有问题，在右边会显示一条线，所以小米手机用户最好设置成“852×480”，其他手机没有测试过，在设置的时候请注意！）。注意：这里两个数字之间的不是乘号，而是字母“xyz”的“x”，输错了不能远程连接的.

然后，提示是否保存你刚才的设置为默认设置，只要输入“y”即可

然后你就可以看到操作完成后光标前的字符变成了“root@localhost:~#”，这样说明你已经成功进入ubuntu系统中了.

远程桌面连接

自行查询VNC的使用说明,在此博主不再赘述. 连接ip:localhost:5900(其中":5900",可填可不填) 密码:ubuntu

退出 Ubuntu 系统

只需要回到刚才我们运行的终端，输入命令 “exit” 回车，等待片刻即可退出 Ubuntu 系统，再次输入 “exit” 回车 则是退出手机终端的 root 用户权限，然后再次 “exit” 回车后则是退出手机终端，这样就完全退出了

下次启动

下次启动的时候只需要开启 终端，然后输入 “su” 获得 root 权限，再输入 “cd /ubuntu” 来到ubuntu文件夹下，然后在输入 “sh bootscript.sh” 运行启动脚本就可以运行启动 Ubuntu 了，需要连接桌面的话按照上面说的用 Android VNC 就可以了。

(其实对于一个服务器系统来说,博主更推荐使用ssh连接来代替VNC连接)

最后补一张最终效果图(此处博主已经自行安装了LXDE桌面环境):

我的算法天梯之路之-归并排序

- -

我的算法天梯之路之-归并排序

插入排序算法采取增量式(Incremental)的策略解决问题,每次添一个元素到已排序的子序列 中,逐渐将整个数组排序完毕,它的时间复杂度是Θ(n2)。下面介绍另一个典型的排序算法– 归并排序,它采取分而治之(Divide-and-Conquer)的策略,时间复杂度是Θ(nlgn),优于插入 排序算法。归并排序的步骤如下:

  1. Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
  2. Conquer: 对这两个子序列分别采用归并排序。
  3. Combine: 将两个排序好的子序列合并成一个最终的排序序列。

在描述归并排序的步骤时又调用了归并排序本身,可见这是一个递归的过程。

示例代码

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

 #include <stdio.h>
 #define LEN 8
 int a[LEN] = {5,2,4,7,1,3,2,6};
 void merge(int start,int mid,int end){
     int n1 = mid - start + 1;
     int n2 = end - mid;
     int left[n1],right[n2];
     int i,j,k;
     for (i = 0;i < n1;i++)
     left[i] = a[start+i];
     for (j = 0;j < n2;j++)
     right[j] = a[mid+1+j];
     i = j = 0;
     for (k = start; i < n1 && j < n2; k++){
         if (left[i] < right[j]){
             a[k] = left[i];
             i++;
         }else{
             a[k] = right[j];
             j++;
         }
     }
     if (i < n1)
     for(;i < n1;i++){
         a[k] = left[i];
         k++;
     }
     if (j < n2)
     for (;j < n2;j++){
         a[k] = right[j];
         k++;
     }
 }
 void sort(int start,int end){
     int mid;
     if (start < end){
         mid = (start + end)/2;
         printf("sort (%d-%d,%d-%d) %d,%d,%d,%d,%d,%d,%d,%d\n",
                start,mid,mid+1,end,
                a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]);
         sort(start,mid);
         sort(mid+1,end);
         merge(start,mid,end);
         printf("merge (%d-%d,%d-%d) %d,%d,%d,%d,%d,%d,%d,%d\n",
                start,mid,mid+1,end,
                a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]);
     }
 }
 int main(){
     sort(0,LEN-1);
     return 0;
 }

在merge函数中演示了C99的新特性–可变长数组,当然 也可以避免使用这一特性,比如把left和right都按最大长度LEN分配。

程序耗时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

$ time ./sort
sort (0-3,4-7) 5,2,4,7,1,3,2,6
sort (0-1,2-3) 5,2,4,7,1,3,2,6
sort (0-0,1-1) 5,2,4,7,1,3,2,6
merge (0-0,1-1) 2,5,4,7,1,3,2,6
sort (2-2,3-3) 2,5,4,7,1,3,2,6
merge (2-2,3-3) 2,5,4,7,1,3,2,6
merge (0-1,2-3) 2,4,5,7,1,3,2,6
sort (4-5,6-7) 2,4,5,7,1,3,2,6
sort (4-4,5-5) 2,4,5,7,1,3,2,6
merge (4-4,5-5) 2,4,5,7,1,3,2,6
sort (6-6,7-7) 2,4,5,7,1,3,2,6
merge (6-6,7-7) 2,4,5,7,1,3,2,6
merge (4-5,6-7) 2,4,5,7,1,2,3,6
merge (0-3,4-7) 1,2,2,3,4,5,6,7

real   0m0.001s
user   0m0.000s
sys    0m0.000s

相比之下冒泡排序在时间复杂度上就较为逊色了,且要排序的元素越多时,差别越大!

示例代码

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

 #include <stdio.h>
 #define LEN 8
 int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };
 void sort(int start, int end)
 {
     int i,j,temp;
     if (start < end) {
         for (i = start;i<end;i++){
             for (j=i+1;j<end;j++){
                 if(a[i] > a[j]){
                 temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
                 }
             }
         }
         printf("sort (%d-%d) %d %d %d %d %d %d %d %d\n",
                start, end,
                a[0], a[1], a[2], a[3], a[4],a[5], a[6], a[7]);

     }
 }
 int main(void)
 {
 sort(0, LEN);
 return 0;
 }

程序耗时

1
2
3
4
5
6

$ time ./sort2
sort (0-8) 1 2 2 3 4 5 6 7

real   0m0.002s
user   0m0.000s
sys    0m0.000s

Gdb的简单使用

- -

gdb的简单使用

1.单步执行和跟踪函数调用

测试源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 #include <stdio.h>
 int add_range(int low,int high)
 {
    int i,sum;
    for (i=low;i<=high;i++)
    {
        sum = sum + i;
    }
    printf("sum = %d\n",sum);
    return sum;
 }
 int main()
 {
    int result[100];
    result[0]=add_range(1,10);
    result[1]=add_range(1,100);
    printf("result[0]=%d \n result[1]=%d \n",result[0],result[1]);
    return 0;
 }

在编译并运行以上代码后,我们会发现最后的输出结果并非如我们预料一样. 无论是result[0]或result[1]基本都是错误的结果,然而代码中的逻辑却没有任何的问题. 在这里心细的朋友可能已经发现问题的所在了. 但既然是练习gdb的使用,那么我们就加上 -g 选项,再重新编译一次代码以便生成的可执行文件可以用gdb进行调试.

$ gcc -g main.c -o main $ gdb main

注:-g选项的作用是在可执行文件中加入源代码的信息,比如可执行文件中第几条机器指令对应源代码的第几行,但并不是把整个源文件嵌入到可执行文件中,所以在调试时必须保证gdb能找到源文件

除此之外,gdb提供一个类似shell的命令行环境,上面的 (gdb) 就是提示符,在这个提示符下输 入help可以查看命令的类别.

help命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(gdb) help
List of classes of commands:

aliases -- Aliases of other commands
breakpoints -- Making program stop at certain points
data -- Examining data
files -- Specifying and examining files
internals -- Maintenance commands
obscure -- Obscure features
running -- Running the program
stack -- Examining the stack
status -- Status inquiries
support -- Support facilities
tracepoints -- Tracing of program execution without stopping the program
user-defined -- User-defined commands

Type "help" followed by a class name for a list of commands in that class.
Type "help all" for the list of all commands.
Type "help" followed by command name for full documentation.
Type "apropos word" to search for commands related to "word".
Command name abbreviations are allowed if unambiguous.
(gdb)

list命令 list命令用于列出代码或指定函数,列出的代码行的起始位置为上一次列出的代码的结尾, 第一次使用时,默认从第一行开始.每次默认列出十行代码.list命令也可简写成l. 要是要列出指定函数的代码,直接在list后面加函数名即可.

eg: list add_range

且可以通过 show listsize 和 show listsize NUM(NUM为整数)来查询和修改每次最大列出代码行数.

在什么都不输入的情况下敲击回车,gdb默认会执行上一条命令

quit命令 退出gdb环境

start命令 开始执行程序,start命令默认停在main函数变量定义后的第一条语句,并等待下一次命令.

next命令(简写n) 单步步过

step命令(简写s) 单步步入

backtrace命令(简写bt) 查看函数调用栈帧

info命令(简写i) 查询相关信息

eg:查询add_range函数局部变量的值,i locals

print命令(简写p) 打印指定变量值

finish命令 执行到返回

介绍完以上几个简单的命令之后再返回到测试代码的调试之中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(gdb) start
Temporary breakpoint 1 at 0x80484c7: file ./gdbtest2.c, line 13.
Starting program: /home/ef/c/gdbtest2

Temporary breakpoint 1, main () at ./gdbtest2.c:13
13    {
(gdb) n
15        result[0]=add_range(1,10);
(gdb) s
add_range (low=1, high=10) at ./gdbtest2.c:5
5     for (i=low;i<=high;i++)
(gdb) bt
#0  add_range (low=1, high=10) at ./gdbtest2.c:5
#1  0x080484de in main () at ./gdbtest2.c:15
(gdb) i locals
i = -1208074951
sum = -1208114904

在以上最后两行输出我们可以明白,程序之所以没有输出我们预期的结果, 其根本原因就是因为局部变量i和sum没有进行初始化.虽然变量i会在for循环之前进行重新赋值, 但作为累积变量的sum由于初始值不是0,导致最后的累加结果错误.

找出错误的所在后,我们即可以退出gdb,修改源码再重新进行调试;或者直接通过gdb的命令

set var sum = 0

修改局部变量sum的值,然后再寻找下一处Bug.

2.断点的使用

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13

 #include <stdio.h>
 int main(void)
 {
  int sum = 0, i = 0;
  char input[5];
  while (1) {
  scanf("%s", input);
  for (i = 0; input[i] != '\0'; i++)
  sum = sum*10 + input[i] - '0';
  printf("input=%d\n", sum);
  }
  return 0;
 }

编译以上代码并运行

1
2
3
4
5
6

$ gcc main.c -g -o main
$ ./main
123
input=123
234
input=123234

我们发现程序第一次运行是对的,但第二次却又出乎了我们意料. 于是我们也把这个程序也放入gdb中调试.

display命令 display命令可以使得每次停下来的时候都显示执行变量的值,亦称变量跟踪.

undisplay命令 取消之前设置的变量跟踪

break命令(简称b) 在指定位置设定断点,参数可以是指定行也可以是某个函数

i breakpoints 输出目前已有断点的信息

enable breakpoints NUM(NUM为断点号) 启用指定断点(NUM为空时,默认为全部断点)

disable breakpoints NUM(NUM为断点号) 禁用指定断点(NUM为空时,默认为全部断点)

delete breakpoints NUM(NUM为断点号) 删除指定断点(NUM为空时,默认为全部断点)

continue命令(简称c) 继续执行,注意,continue命令是连续运行而非单步执行.

介绍完命令后我们又再次回到调试中,首先我们执行完start命令后,使用

b 9

在sum的赋值处下一个断点,并用命令

display sum

来时刻监视变量sum的变化
这时我们发现在我们输入完"123"后,再次想输入"456"时,gdb显示 “sum = 123” ,这样我们便发现错误所在,即我们并没有在新的循环中清空sum的先值

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

(gdb) start
Temporary breakpoint 1 at 0x804848c: file ./gdbtest3.c, line 3.
Starting program: /home/ef/c/gdbtest3

Temporary breakpoint 1, main () at ./gdbtest3.c:3
3 {
(gdb) list
1 #include <stdio.h>
2 int main(void)
3 {
4 int sum = 0, i = 0;
5 char input[5];
6 while (1) {
7 scanf("%s", input);
8 for (i = 0; input[i] != '\0'; i++)
9 sum = sum*10 + input[i] - '0';
10    printf("input=%d\n", sum);
(gdb) b 9
Breakpoint 2 at 0x80484c2: file ./gdbtest3.c, line 9.
(gdb) display sum
1: sum = 134514011
(gdb) c
Continuing.
123

Breakpoint 2, main () at ./gdbtest3.c:9
9 sum = sum*10 + input[i] - '0';
1: sum = 0
(gdb) c
Continuing.

Breakpoint 2, main () at ./gdbtest3.c:9
9 sum = sum*10 + input[i] - '0';
1: sum = 1
(gdb) c
Continuing.

Breakpoint 2, main () at ./gdbtest3.c:9
9 sum = sum*10 + input[i] - '0';
1: sum = 12
(gdb) c
Continuing.
input=123
456

Breakpoint 2, main () at ./gdbtest3.c:9
9 sum = sum*10 + input[i] - '0';
1: sum = 123
(gdb)