如何提高编程能力？(中)
- 2019 年 10 月 5 日
- 筆記
17.求近似数
17.1 牛顿迭代法
如定积分、用牛顿迭代法或二分法或弦截法求多元方程的根
#include<stdio.h> #include<math.h> double func(double x) { return x*x*x*x - 3 * x*x*x + 1.5*x*x - 4.0; } double func1(double x) { return 4 * x*x*x - 9 * x*x + 3 * x; } int Newton(double *x,double precision,int maxcyc) { double x1, x0; int k; x0 = *x; for (k = 0; k < maxcyc; k++) { if (func1(x0) == 0.0) { printf("迭代过程中导数为0!n"); return 0; } x1 = x0 - func(x0) / func1(x0); if (fabs(x1-x0) < precision || fabs(func(x1)) < precision) { *x = x1; return 1; } else { x0 = x1; } } printf("迭代次数超过预期!n"); return 0; } int main() { double x, precision; int maxcyc; printf("输入初始迭代值x0:"); scanf("%lf",&x); printf("输入最大迭代次数:"); scanf("%d", &maxcyc); printf("迭代要求的精度:"); scanf("%lf", &precision); if (Newton(&x, precision, maxcyc) == 1) { printf("该值附近的根为:%lfn", x); } else { printf("迭代失败!n"); } return 0; }
17.2 精简版
//精简版 #include<stdio.h> #include<math.h> double fun(double x) { return 2*x*x*x - 4*x*x + 3*x - 6; } double fun1(double x) { return 6*x*x - 8 * x + 3.0; } int main() { double x, x0, f,f1,precision; printf("请输入初始x0:"); scanf("%lf",&x); printf("请输入精度precision:"); scanf("%lf",&precision); do { x0 = x; f=fun(x0); } while (fabs(x-x0)>= precision); printf("%lfn",x); return 0; }
17.3 二分法
- 1 确定区间[a,b],验证f(a)·f(b)<0
- 2 求区间(a,b)的中点x
- 3 判断 (1) 若f(a)·f(c)<0,则令b=x; (2) 若f(x)·f(b)<0,则令a=x.
- 4 判断f(x)是否达到精确度ξ:即若┃f(c)┃<ξ，则x=c就是使f(x)接近零点的近似值，否则重复2-4.
#include<stdio.h> #include<math.h> int main() { double func(double x); double root(double a, double b); root(-10,10); return 0; } double func(double x) { return 2 * x*x*x - 4 * x*x + 3 * x - 6.0; } double root(double a, double b) { double x; double a1=a, b1=b; x = (a + b) / 2; if(func(x)==0.0) { printf("该方程在%lf到%lf区间内的根为:%lf.n",a1,b1,x); return x; } else { while (fabs(a - b) > 1e-6) { if (func(a)*func(x) < 0) b = x; else a = x; x = (a + b) / 2; } } printf("该方程在%lf到%lf区间内的根为:%lf.n", a1, b1, x); return x; }
17.4 弦截法
函数方程： y – f2 = (f2 – f1) / (x2 – x1)(x – x2) 化简得: x=(f2x1-f1x2)/(f2-f1)
#include<stdio.h> #include<math.h> double xpoint(double x1, double x2); //弦与x轴的交点横坐标 double root(double x1, double x2); //求根函数 double f(double x); //求x点的函数值 int main() { double x1, x2, f1, f2, x; do { printf("请输入x1,x2:"); scanf("%lf,%lf",&x1,&x2); f1 = f(x1); f2 = f(x2); } while (f1*f2>=0); //当循环运算到f(x1)*f(x2)>=0时(0是必要条件参数)，即f(x1)、f(x2)同符号，且任一个接近于0时，意味着与x轴接近相交，此时存在一个方程实根。 x = root(x1,x2); printf("方程的一个解为：%.2fn",x); return 0; } double xpoint(double x1, double x2) { double x = 0; x = (x1*f(x2)-x2*f(x1)) / (f(x2)-f(x1)); return x; } double root(double x1,double x2) { double x, y, y1, y2; y1 = f(x1); y2 = f(x2); do { x = xpoint(x1,x2); y = f(x); if (y*y1 > 0) { x1 = x; y1 = y; } else { x2 = x; y2 = y; } } while (fabs(y)>=0.00001); return x; } double f(double x) { double y = 0; y = x*x*x - 5 * x*x + 16 * x - 80; return y; }
18.矩阵运算及二维数组
18.1 求两个矩阵之和、之积
#include<stdio.h> #define N 2 int main() { void print(int(*a)[N]); void vx(int(*a)[N], int(*b)[N]); int i, j; int a[N][N],b[N][N]; printf("输入两个矩阵:n"); printf("矩阵1:n"); for (i = 0; i < N; i++) for (j = 0; j < N; j++) scanf("%d",&a[i][j]); printf("---------n"); print(a); printf("矩阵2:n"); for (i = 0; i < N; i++) for (j = 0; j < N; j++) scanf("%d", &b[i][j]); printf("---------n"); print(b); vx(a,b); return 0; } void vx(int (*a)[N],int (*b)[N]) { void print(int(*a)[N]); int i,j,k,res; int c[N][N],d[N][N]; for (i = 0; i < N; i++) for (j = 0; j < N; j++) { res = 0; c[i][j] = a[i][j] + b[i][j]; for(k=0;k<N;k++) res += a[i][k] * b[k][j]; d[i][j]=res; } printf("两矩阵相加:n"); print(c); printf("两矩阵相乘:n"); print(d); } void print(int (*a)[N]) { int i,j; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) printf("%d ",a[i][j]); printf("n"); } }
18.2 二维数组
二维数组某位置上的元素在该行上最大，该列上最小
#include<stdio.h> int main() { int a[4][5]; int i, j, k, m; for (i = 0; i < 4; i++) for (j = 0; j < 5; j++) scanf("%d",&a[i][j]); for (i = 0; i < 4; i++) { for (j = 0; j < 5; j++) { //扫描行，确定行中最大值 for (k = 0; k < 5; k++) { if (a[i][j] < a[i][k]) { break; } } if (k == 5) { //扫描列，确定列中最小值 for (m = 0; m < 4; m++) { if (a[i][j] > a[m][j]) break; } if (m == 4) printf("满足值:%d ",a[i][j]); } } } return 0; }
19.位运算及应用
19.1 位运算
- 1.与 & 1&0=0;0&0=0;1&1=1;
- 2.或 | 1|0=1;0|0=0;1|1=1;
- 3.非 ~ ~1=-2 ~16=-17 00010000 16二进制数 11101111 16二进制数取非运算 取反+1即： 00010000+1=00010001=-17
- 4.异或 1^0=1;0^0=0;1^1=0
19.2 一个字节中被置为1的位的个数
#include<stdio.h> int main() { int sum = 0; //题中给出一个字节，则占8位，取值范围为0~255 int a; printf("请输入一个字节的数，以十进制输入:n"); scanf("%d",&a); if (a < 0 || a>255) { printf("errorn"); return 1; } int i, k=1; for (i = 1; i < 9; i++) { if (a == (a | k)) sum++; k *= 2; } printf("共%d位n",sum); return 0; }
20.排序算法
20.1 快速排序
void sort(int *p, int low, int high) { if (low > high) return; int temp, i, j, t; temp = p[low]; i = low; j = high; while (i < j) { while (i<j&&p[j]>=temp) j--; while (i < j&&p[i] <= temp) i++; if (i < j) { t = p[i]; p[i] = p[j]; p[j] = t; } } p[low] = p[i]; p[i] = temp; sort(p,low,i-1); sort(p,i+1,high); }
20.2 冒泡排序
void sort(int *p, int n) { int i, j; int t; for (i = 0; i < n - 1; i++) { for(j=0;j<n-i-1;j++) { if (p[j] > p[j + 1]) { t = p[j]; p[j] = p[j+1]; p[j + 1] = t; } } } }
20.3 选择排序
void sort(int *p, int n) { int i, j, k, temp; for (i = 0; i < n-1; i++) { k = i; for (j = i; j < n; j++) { if (p[k] > p[j]) k = j; } temp = p[i]; p[i] = p[k]; p[k] = temp; } }
20.4 直接插入排序
void sort(int *p, int n) { int i,j,k,t; for(i=1;i<n;i++) //注意从第2个元素操作 { if(p[i]<p[i-1]) { t=p[i]; for(j=i-1;j>=0&&p[j]>t;j--) { p[j+1]=p[j]; } } p[j+1]=t; } } //换成字符操作 void sort(char *p) { int i,j,n; char ch; n=strlen(p); for(i=i;i<n;i++) { ch=p[i]; j=i-1; while((j>=0)&&(ch<p[j])) { p[j+1]=p[j]; j--; } p[j+1]=ch; } }
21.链表
21.1 单链表之增删改查
/*单链表*/ #include<stdio.h> #include<malloc.h> typedef struct Node { int data; struct Node *PNext; }Node, *PNode; #define ERROR 0 #define OK 1 PNode create_list() { int len, i; printf("请输入链表的长度:len=n"); scanf("%d",&len); PNode PHead = (PNode)malloc(sizeof(Node)); PHead->PNext = NULL; PNode PTail=PHead; for (i = 0; i < len; i++) { int val; printf("请输入第%d个元素的值:",i+1); scanf("%d",&val); PNode PNew = (PNode)malloc(sizeof(Node)); PNew->data = val; PNew->PNext = NULL; PTail->PNext=PNew; PTail = PNew; } return PHead; } void outLink(PNode pHead) { PNode p = pHead->PNext; while (p) { printf("%d ",p->data); p = p->PNext; } putchar('n'); } PNode reverse(PNode pHead) { PNode p = pHead->PNext; PNode q,r; q = p->PNext; p->PNext = NULL; while (q) { r = p; p = q; q = p->PNext; p->PNext = r; } pHead->PNext = p; return pHead; } int list_num(PNode pHead) { int num = 0; PNode p = pHead->PNext; while (p) { num++; p = p->PNext; } return num; } //pos从1开始 /* 12345 有6个插入位置 */ int insert_list(pnode phead, int val, int pos) { int i; pnode p = phead->pnext; int length = list_num(p); if (pos<1 || pos>length+2) return error; else { i = 0; //定位到pos前一位,在下标pos-1处插入结点，需要知道前一结点 while (p&&i < pos - 2) { i++; p = p->pnext; } if (p||(i == pos - 2)) { pnode pnew = (pnode)malloc(sizeof(pnode)); pnew->data = val; if (pos == 1) { pnew->pnext = p; phead->pnext = pnew; } else if (pos == length+2) { p->pnext = pnew; pnew->pnext=null; } else { pnew->pnext = p->pnext; p->pnext = pnew; } length++; return ok; } else return error; } } int insert_list(PNode pHead, int val, int pos) { PNode p = pHead; int length = list_num(p),i; if (pos<0 || pos>length ||!p) return ERROR; else { i = -1; while (p&&i < pos - 1) { i++; p=p->PNext; } if (i == pos - 1 || p) { PNode PNew = (PNode)malloc(sizeof(PNode)); PNew->data = val; if (i == -1) { PNew->PNext = pHead->PNext; pHead->PNext = PNew; } else if (pos == length) { p->PNext = PNew; PNew->PNext = NULL; } else { PNew->PNext = p->PNext; p->PNext = PNew; } length++; return OK; } else return ERROR; } } //删除,根据结点值删除 int delData(PNode pHead, int *val) { int length = list_num(pHead); PNode p = pHead,q; if (!p) return ERROR; while (p->PNext!=NULL) { if (p->PNext->data == *val) { q = p->PNext; p->PNext = p->PNext->PNext; free(q); } else p = p->PNext; } return OK; } //删除，按照位置删除,且pos从1开始 int delpos(PNode pHead, int pos) { PNode q = pHead; PNode p = q->PNext; int length = list_num(pHead); if (pos<1 || pos>length) return ERROR; else { int i = 1; while (i < pos - 1) { i++; q = p; p = p->PNext; } if (pos == 1) pHead->PNext = pHead->PNext->PNext; else if (pos == length) q->PNext = NULL; length--; return OK; } } //或者pos从0开始计算 /*12345 有0~length范围可插入 */ int main() { int num; PNode PHead = create_list(); outLink(PHead); num = list_num(PHead); putchar('n'); printf("共有%d个结点.n", num); PNode rp = reverse(PHead); outLink(rp); int val; printf("请输入插入结点的值："); scanf("%d", &val); int pos; printf("请输入插入结点的位置(从1开始)："); scanf("%d", &pos); int flag = insert_list(rp, val, pos); if (flag == 1) { printf("插入结点成功,共%d个结点n", list_num(rp)); outLink(rp); } else printf("插入失败.n"); int data; printf("请输入要删除的结点值:"); scanf("%d", &data); int f = delData(rp, &data); if (f == 1) { printf("删除%d成功!n", data); outLink(rp); } else printf("删除结点不存在!n"); int delposi; printf("请输入要删除的位置:"); scanf("%d", &delposi); int f1 = delpos(rp, delposi); if (f1 == 1) { printf("删除第%d个位置成功!n", delposi); outLink(rp); } else printf("删除位置不存在!n"); }
21.2 头插法
头插法思路：先判断是否为head结点，若为head结点，则将新造的结点先赋值，然后链接在head后面，并将此时结点的next设为空，因为此时表示末尾结点，否则会出错！！！ 此次结束后，将p指向q所指的结点，然后新造结点将q结点的next链接到p，在往前，最后用将p结点链接至head结点后面即可！
node * createlist() { int n; node *head = (node *)malloc(sizeof(node)); node *p = head; head->next = NULL; if (head == NULL) { printf("申请空间失败！n"); return NULL; } else { printf("请输入结点个数,n="); scanf("%d",&n); int i,num; for (i = 0; i < n; i++) { printf("请输入第%d个结点数值:n",i+1); scanf("%d",&num); node *q = (node *)malloc(sizeof(node)); if (p == head) { head->next = q; q->data = num; q->next = NULL; } else { q->data = num; q->next = p; } p = q; } head->next = p; } return head; }
21.3 链表逆置
NODE *reverseList(NODE *h) { NODE *p, *q, *r; p = h; if (!p) return NULL; q = p->next; p->next = NULL; while (q) { r = q->next; q->next = p; p = q; q = r return p; }
