2019.12.01-2019.12.07

发表于 更新于 阅读次数：

1.洛谷-P1028 数的计算

在这里插入图片描述

第一次写的时候大概思路：在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
int cal(int n) {
	int sum=1;
	if(n==1)
		return sum;
	for(int i=1; i<=n/2; i++)
		sum=sum+cal(i);
	return sum;
}
int main() {
	int n;
	scanf("%d",&n);
	printf("%d",cal(n));
	return 0;
}

结果有15个超时了。
前几天看别人的题解没看懂，打算写完周报再看一下。

2.递归优化

有关递归的一些优化思路1. 考虑是否重复计算告诉你吧，如果你使用递归的时候不进行优化，是有非常非常非常多的子问题被重复计算的。 啥是子问题？ f(n-1),f(n-2)…就是 f(n) 的子问题了。例如对于案例2那道题，f(n) = f(n-1) + f(n-2)。递归调用的状态图如下：看到没有，递归计算的时候，重复计算了两次 f(5)，五次 f(4)。。。。这是非常恐怖的，n 越大，重复计算的就越多，所以我们必须进行优化。如何优化？一般我们可以把我们计算的结果保证起来，例如把 f(4) 的计算结果保证起来，当再次要计算 f(4) 的时候，我们先判断一下，之前是否计算过，如果计算过，直接把 f(4) 的结果取出来就可以了，没有计算过的话，再递归计算。用什么保存呢？可以用数组或者 HashMap 保存，我们用数组来保存把，把 n 作为我们的数组下标，f(n) 作为值，例如 arr[n] = f(n)。f(n) 还没有计算过的时候，我们让 arr[n] 等于一个特殊值，例如 arr[n] = -1。当我们要判断的时候，如果 arr[n] = -1，则证明 f(n) 没有计算过，否则， f(n) 就已经计算过了，且 f(n) = arr[n]。直接把值取出来就行了。代码如下：// 我们实现假定 arr 数组已经初始化好的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int n){
    if(n <= 1){
        return n;
    }
    //先判断有没计算过
    if(arr[n] != -1){
        //计算过，直接返回
        return arr[n];
    }else{
        // 没有计算过，递归计算,并且把结果保存到 arr数组里
        arr[n] = f(n-1) + f(n-1);
        reutrn arr[n];
    }
 }

也就是说，使用递归的时候，必要 须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。2. 考虑是否可以自底向上对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。不过，有时候当 n 比较大的时候，例如当 n = 10000 时，那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道f(1) = 1;f(2) = 2;那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来取代递归，代码如下：

int f(int n) {
1
2
3
4
5
6
7
8
9
10
11
12
13
public int f(int n) {
       if(n <= 2)
           return n;
       int f1 = 1;
       int f2 = 2;
       int sum = 0;
       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
        }

这种方法，其实也被称之为递推。
作者：帅地
链接：https://www.zhihu.com/question/31412436/answer/683820765
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.链表的查找

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
void find(struct stud *p) {
	struct stud *p1=p;
	int num=0;
	char name[10];
	int flag=0;
	printf("find:1.num or 2.name?   ");
	scanf("%d",&num);
	
	if(num==1) {
		printf("type a name:   ");
		scanf("%s",name);
		getchar();
			while(p1->next!=NULL){
			if(strcmp(name,p1->name)!=0){
				p1=p1->next;
				num++;
			}
			else{
				printf("%d\n",num);
				flag=1;
			}
		}
		if(flag==0)
			printf("not found\n");
	}
int i=0;
if(num==2) {
		printf("type a number:   ");
		scanf("%d",&num);
		while(i!=num&&p1->next!=NULL){
			p1=p1->next;
		}
		if(p1->next==NULL)
			printf("wrong number");
		else
			printf("%s\n",p1->name);

	}
}

最开始写的时候把num和name[10]放在一个共用体里，没考虑到共用体里只能有一个成员有值…

3.汇编语言学习：

1-存储单元：

bit（一个二进制位），8位bit，8个bit组成一个byte（字节）

2-cpu对存储器的读写：

和外部器件进行三类信息交互：

	1.存储单元的地址（地址信息）；
	2.器件的选择，读或写（控制信息）；
	3.读或写的数据（数据信息）；
cpu通过总线传输信息，总线分为：地址，， 控制，， 数据，，
一个cpu有n根地址线，可一次传送n位二进制数据，地址总线宽度为n，
这样的cpu 最多可以对2^n个内存单元进行寻址
控制总线  ：“读信号输出”	“写信号输出”

存储器芯片：

读写属性：随机存储器（ram）只读存储器（rom）
功能和连接：
	随机存储器，存放供cpu使用的绝大部分程序和数据
	接口卡上的ram，如显存
	装有bios的rom（在主板和各类接口卡上，如显卡，网卡）

内存地址空间：
内存地址空间地址段分配
基于硬件系统编程必须知道这个系统中的内存地址空间分配情况，想在某类存储器中读写数据的时候必须知道它的第一个单元的地址和最后一个单元的地址
在这里插入图片描述

3-汇编指令：

不区分大小写

mov ah,78 == 将18送入寄存器ax
mov ax,bx == 将寄存器bx中的数据送入寄存器ax
add ax,bx == 将ax和bx中的数值相加，结果存在ax中

ax中数值为00C5H，执行add al，93H 后，ax中数据为：0058H，不为0058H，因为此时al是作为一个独立的8位寄存器，与ah没有关系。

8086cpu
16位结构（16位机、字长为16位）：
1.运算器一次最多可以处理16位的数据
2.寄存器的最大宽度为16位
3.运算器和寄存器之间的通路为16位

两个16位地址（段地址、偏移地址）合成一个20位物理地址
段地址和偏移地址通过内部总线送入地址加法器，合成后通过内部总线–>输入输出控制电路–>地址总线–>存储器
地址加法器中，物理地址=段地址 *16+偏移地址
（段地址 *16表现为16进制时向左移一位，2进制时移动4位）
（一个x进制的数据向左移动n位，相当于乘以x^n)

内存没有分段，段的划分来自于cpu，cpu可以用不同段地址和偏移地址形成同一个物理地址
对于8086pc机，“数据在21F60H内存单元中”=“数据存在内存2000：1F60单元中”=“数据存在内存的2000H段中的1F60H单元中”

4.-段寄存器（segment register）

提供段地址
6个段寄存器：
cs（code）
ds（data）
ss（stack）
es（extra）
*32位：fs（flag）gs（global）

5-CS、IP

cs为代码段寄存器，IP为指令指针寄存器
物理地址=CS *16+IP

cpu读取指令后，指令进入指令缓冲器，IP的值自动增加，增加长度等于当前读入指令长度

cpu刚开始工作时，CS=FFFFH,IP=0000H,即从FFFF0H单元读取指令执行。
改变CS、IP的值的指令统称为转移指令，如jmp
同时修改CS、IP:jmp 段地址:偏移地址
只修改IP:jmp 某一合法寄存器（如ax/bx）在含义上好似： mov IP,ax

6-字单元：

存放一个字型数据（16位）的内存单元，由两个地址连续的内存单元组成，高地址内存单元中存放字型数据的高位字节，，，，，
起始地址为n的字单元简称为n地址字单元