动态规划基础练习 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? Input 输入数据首先包括一个整数C,表示数据的个数。 每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。 Output 对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。 Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 思路: 一个结点有两个相邻的结点,所以子问题就是以相邻结点为根,从根走向叶经过数字的最大和, 那么原来的问题既可以转化为 根上的数字加上两个子问题的最大值 ​ 那么动态转移方程就可以写出来了:acc[i][j] = num[i] 继续阅读 >>


张小翔 18/08/13 00:08:44
线程初探 [1] 线程 线程 线程是计算机独立运行(操作系统分配CPU时间的基本单位)的最小单位,运行时占用很少的系统资源 单cpu单核:多个线程是交替执行的 多cpu多核:多个线程可以同时运行 同一进程内的多个线程共享进程的地址空间 线程之间的切换速度比进程的切换快很多 进程通信要以专门的通信方式、一个线程的数据可以直接供同一进程的其他线程使用 线程节约资源、节约时间、可以提高应用程序的响应速度、可以提高多处理器效率、改善程序的结构 线程在进程内部共享的资源: 地址空间、打开的文件描述符等待 线程的私有数据: 线程号 寄存器(程序计数器、堆栈指针) 栈 信号掩码 优先级 私有的存储空间 自己的错误返回码 线程有自己的栈但是共享 堆(heap) We talked about the two types of memory available to a process or a thread, the stack and the heap. It i 继续阅读 >>


张小翔 18/08/09 21:30:59
readline库的简单使用 这周要实现一个简单的 shell, 平时使用bash, zsh这些shell的时候, 如果文件名或命令太长,又或者要频繁执行几条命令的话,最常用的应该就是tab键补全和上下键切换历史命令了。 想要在自己的shell里面实现这两个功能很困难,但有一个C语言库集成了这些功能,只需要调用几个函数就可以实现这两个功能。 The GNU Readline Library 可以在这里找到有关 readline 库的相关资料和下载地址,软件包里面也提供了很多手册和示例。 实现shell用到的函数不是很多,tab键补全,上下键切换历史命令,添加历史命令等等 readline() 在 readline.h 里可以找到关于他的定义: /* Readline functions. */ /* Read a line of input. Prompt with PROMPT. A NULL PROMPT means none. */ extern char *readl 继续阅读 >>


张小翔 18/08/05 22:44:23
基本搜索算法(DFS|BFS) 这周的题目中设计到的算法:DFS 和 BFS 都是基本的图算法,图是一种数据结构,可以表示出节点之间的关系。 基本搜索算法有两种策略: 深度优先 广度优先 [1] 深度优先搜索 我们对一个图进行搜索,无非就是寻找某种状态,深度优先顾名思义,就是寻找某种状态的时候选择一条路走到底,走不通就退回去换另一条路。 就像走迷宫那样,我们把迷宫抽象为一个图,路就是图里面的边,路两端的地方抽象为节点。走出这个迷宫就可以看作是我们要寻找的一个状态,在不清楚迷宫构造和不破换游戏规则的情况下,找到出口只能一个一个去尝试,为了不出现在同一条路上绕来绕去的尴尬情况,我们需要标记过我们到过的地方,然后一直往深处走,走到头若发现此路不通或已经走过,那自然就要原路返回到前一个岔路口去走另一条路。这种方法虽然比较笨比较低效,但只要迷宫有出口就一定可以出的去。 有了这个例子,很容易归纳出深度优先的基本方法: 选择一个初始节点 从这个初始节点开始寻找,标记走过的节点 如果走到不能再 继续阅读 >>


张小翔 18/08/05 17:58:17
这周要写一个小项目,利用《linux C 编程实战》第6章的内容实现一个简单的 ls 命令,写的时候出现很多问题,现在将问题总结一下。 要实现的ls命令需要实现 -l, -a , -A 等参数。 我们在终端测试一下系统的ls命令: 可以发现系统的ls可以根据终端的宽度来调整输出列数,而不至于输出的内容由于终端大小的限制显示不全。 如果想要实现类似的功能,首先需要获取终端的宽度,然后计算输出文件列表的最大列数,最后按列将文件输出到屏幕上。 终端宽度的获取 查了很多,发现书上提到的 int ioctl(int fd, int cmd, ...)可以实现这个功能, 先放出代码: // 获取终端宽度 int get_ter_size (void) { struct winsize w; ioctl(STDOUT_FILENO, TIOCGWINSZ, &w); return w.ws_col; } ioctl 可以控制特殊设备文件的属性,第一个参数 继续阅读 >>


张小翔 18/07/29 15:58:44
1