- 1Linux功耗管理(18)_Linux cpuidle framework(1)_概述和软件架构_linux cpuidle wfi
- 2android安卓记事本课设_安卓记事本app课程设计
- 3如何保护您的SpringBoot项目：防止源代码泄露，确保更安全的部署_spring 泄露
- 4Hadoop单机环境搭建_hadoop单机版访问hdfs
- 5数据资产管理的艺术：构建智能化、精细化的数据资产管理体系，从数据整合、分析到决策支持，为企业提供一站式的数据资产解决方案，助力企业把握数字时代的新机遇
- 6论文《Learning the quantum algorithm for state overlap 》阅读笔记
- 7智能信息检索——期末复习题库_在 10,000 篇文档构成的文档集中,某个查询的相关文档总数为 10,下面给出了某系 统
- 8Lianwei 安全周报|2024.07.01
- 9华为OD 技术综合面，手撕代码真题整理（七）：字符串的不重复子串 | 二叉树的最大路径和_华为od面试手撕代码python
- 10ELK笔记
BUAA 2019 数据结构第一次上机_北航数据结构上机
赞
踩
BUAA 2019 数据结构第一次上机
虽然数据结构已经学完，但感觉学得不是很好，趁着现在有时间，整理一下以前上机的题目.
1 表达式计算（支持空格，连乘，连除）
【问题描述】
从标准输入中读入一个整数算术运算表达式，如5 - 1 * 2 * 3 + 12 / 2 / 2 = 。计算表达式结果，并输出。
要求：
1、表达式运算符只有+、-、*、/，表达式末尾的’=’字符表示表达式输入结束，表达式中可能会出现空格；
2、表达式中不含圆括号，不会出现错误的表达式；
3、出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。
【输入形式】
在控制台中输入一个以’=’结尾的整数算术运算表达式。
【输出形式】
向控制台输出计算结果（为整数）。
【样例1输入】
5 - 1 * 2 * 3 + 12 / 2 / 2 =
【样例1输出】
2
【样例2输入】
500 =
【样例2输出】
500
【样例1说明】
输入的表达式为5 - 1 * 2 * 3 + 12 / 2 / 2 =，按照整数运算规则，计算结果为2，故输出2。
【样例2说明】
输入的表达式为500 = ，没有运算符参与运算，故直接输出500。
算法之一提示：
1、可以利用gets函数，读取整行表达式；
2、对于空格，可以考虑首先去除表达式中的所有空格
3、可以设一计数器用来记录已读取、但未参加运算的运算符的个数，根据该计数器来判断如何进行运算；
4、可以设计一函数：实现二元整数算术运算。
【评分标准】
该题要求输出整数表达式的计算结果，共有5个测试点。上传C语言文件名为example1c.c。
思路：
这题没有括号，难度是初级。 下面说说思路：
我们建立两个栈，一个用来存数字，一个用来存操作符，如： + , - , * , / 但需要注意的是操作符运算的优先级 即先乘除，后加减
那么我们就在压栈的时候把乘除操作做完（即取数字栈栈顶的两个数字，对其进行乘 / 除)， 并把乘除操作后的数字压入栈中这个很重要
需要注意的是，在下面的代码中是先判断符号栈栈顶是不是乘除号，后把当前读入符号压入栈中，也就意味着最后一次压入的操作符可能是乘除号，我们需要在此做特殊操作
经过以上操作之后，符号栈中只有加减号了，那么直接对栈中元素遍历，就完事了。
这个题就只考察了栈的概念和基本操作。嗯，就这样。
题解：
不要照搬，查重还是很厉害的
#include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> #include <math.h> char opt[12315]; int top1,top2; char s[12315]; long long stack[12315]; int main() { int i; long long temp; scanf("%[^=]",&s); //读入 = 前的字符串 int len = strlen(s); for(i = 0; i < len; i++) { temp = 0; if(s[i] == ' ') continue; //若是' ' 跳过 if(s[i] >= '0' && s[i] <='9') // 读入数字 { while(s[i] >= '0' && s[i] <='9') temp = temp*10 + s[i++] - '0'; stack[++top1] = temp; //将当前读入的数字压如栈 i--; //为什么要i--呢， 因为前面多加了一个 } else { char opts = s[i]; //读入操作符 if( (opt[top2] == '*'|| opt[top2] == '/')&&top1>=2&&top2>=1) //如果符号栈栈顶为乘除，先算乘除，此时要求数字栈有至少2个数 { if(opt[top2] == '*') temp = stack[top1-1]*stack[top1]; //取出栈顶两个数字进行计算 else temp = stack[top1-1]/stack[top1]; top1--; top2--; stack[top1] = temp; //把计算结果压入栈中 } opt[++top2] = opts; // 把本次读入的操作符压入栈中 } } if((opt[top2] == '*' || opt[top2] == '/' )&&top1>=2 && top2>=1) //如果最后一次压入符号栈中的数字是乘除 { if(opt[top2]== '*') temp = stack[top1-1]*stack[top1]; else temp = stack[top1-1]/stack[top1]; top1--; top2--; stack[top1] = temp; } temp = stack[1]; //从第一个数开始 for(i = 1; i< top1; i++) { if(opt[i]== '+') temp = temp + stack[i+1]; //运算加减 else temp = temp - stack[i+1]; } printf("%lld",temp); 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
2 扩展字符A
【问题描述】
从键盘输入包含扩展符’-'的字符串，将其扩展为等价的完整字符，例如将a-d扩展为abcd，并输出扩展后的字符串。
要求：只处理[a-z]、[A-Z]、[0-9]范围内的字符扩展，即只有当扩展符前后的字符同时是小写字母、大写字母或数字，并且扩展符后的字符大于扩展符前的字符时才进行扩展，其它情况不进行扩展，原样输出。例如：a-R、D-e、0-b、4-B等字符串都不进行扩展。
【输入形式】
从键盘输入包含扩展符的字符串
【输出形式】
输出扩展后的字符串
【输入样例1】
ADEa-g-m02
【输出样例1】
ADEabcdefghijklm02
【输入样例2】
cdeT-bcd
【输出样例2】
cdeT-bcd
【样例说明】
将样例1的输入ADEa-g-m02扩展为：ADEabcdefghijklm02；样例2的输入cdeT-bcd中，扩展符前的字符为大写字母，扩展符后的字符为小写字母，不在同一范围内，所以不进行扩展。
【评分标准】
该题要求扩展字符，提交程序文件expand.c。
思路：
水题，不想讲什么思路了，简单判断一下就行。
题解：
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> char *low = "abcdefghijklmnopqrstuvwxyz"; //把大写字母，小写字母，数字写进数组里 char *upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; char *num = "0123456789"; char s[505]; int main() { scanf("%s",s); //读入字符串 int i; for(i = 0; i< strlen(s);i++) //大家别学，我是懒得改了，一般的话前面定义个int len = strlen(s) { if(s[i] >= 'a' && s[i] <='z') printf("%c",s[i]); //若遇字母，数字，直接输出 if(s[i] >= 'A' && s[i] <='Z') printf("%c",s[i]); if(s[i] >= '0' && s[i] <='9') printf("%c",s[i]); if(s[i] == '-') //若遇'-' 进行讨论 { if(islower(s[i-1])&&islower(s[i+1]) && s[i-1] < s[i+1]) // s[i] 前后两都是小写字母，并且前面的字母的ASCII码比后面小 { char *j; int flag = 0; for(j = low; j< low + 26; j++) //从s[i-1]的字母输出到s[i+1]的字母 { if(*j == s[i+1]) break; if(*j == s[i-1]) {flag = 1;continue;} if(flag == 1) printf("%c",*j); } } else if(isupper(s[i-1])&&isupper(s[i+1]) && s[i-1] < s[i+1]) //判断大写字母 ， 与小写字母同理 { char *j; int flag = 0; for(j = upper; j< upper + 26; j++) { if(*j == s[i+1]) break; if(*j == s[i-1]) {flag = 1;continue;} if(flag == 1) printf("%c",*j); } } else if(s[i-1]>='0'&&s[i-1]<='9'&&s[i+1]>='0'&&s[i+1]<='9' && s[i-1] < s[i+1]) //判断数字，与小写字母同理 { char *j; int flag = 0; for( j = num; j < num +10; j++) { if(*j == s[i+1]) break; if(*j == s[i-1]) {flag = 1;continue;} if(flag == 1) printf("%c",*j); } } else printf("%c",s[i]); } } 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
3 超长正整数的减法
【问题描述】
编写程序实现两个超长正整数（每个最长80位数字）的减法运算。
【输入形式】
从键盘读入两个整数，要考虑输入高位可能为0的情况（如00083）。
- 第一行是超长正整数A；
- 第二行是超长正整数B；
【输出形式】
输出只有一行，是长整数A减去长整数B的运算结果，从高到低依次输出各位数字。要求：若结果为0，则只输出一个0；否则输出的结果的最高位不能为0，并且各位数字紧密输出。
【输入样例】
234098
134098703578230056
【输出样例】
－134098703577995958
【样例说明】
进行两个正整数减法运算， 234098 －134098703578230056 = －134098703577995958。
【评分标准】
完全正确得20分，每个测试点4分，提交程序文件名为subtract.c。
思路：
高精度的模版题。
高精度的思路就是用数组来模拟一个巨大的数字(位数很大的那种),同过对数组的位数的操作达到加，减，乘，除等效果
这个应该是程序设计基础的时候就做过吧。。。 没做过自己想想，也不难，这题也不多说了
注意下面的代码仅仅适用于两个正数相减的情况
题解：
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 5; char s1[maxn],s2[maxn],s3[maxn]; //将两个大数字分别保留在s1,s2中，s3临时用 int a[maxn], b[maxn], c[maxn]; //将s1,s2的每一位转化成数字，存在a,b,中，c中存a,b相减后的结果 // 为方便说，下面说的数字a,数字b，就是从s1,s2读入的数字，别理解歪了，和数组a,数组b区分开 int main(){ scanf("%s%s",s1,s2); int lena = strlen(s1); int lenb = strlen(s2); if(lena < lenb || (lena == lenb && strcmp(s1,s2) < 0)){ //如果数a比数b小，输出负号并交换两个数，做到大数减小数 putchar('-'); strcpy(s3,s1); strcpy(s1,s2); strcpy(s2,s3); int t = lena; lena = lenb; lenb = t; } // 很重要倒着将数字存入int数组中，为什么呢？你想想你算减法的时候是不是从个位往前算的 233 for(int i = 0; i < lena; i++) a[lena - i] = s1[i] - '0'; // from 1 to lena for(int i = 0; i < lenb; i++) b[lenb - i] = s2[i] - '0'; // from 1 to lenb int i = 1; while( i <= lena && i <= lenb){ if(a[i] - b[i] < 0) {a[i] += 10; a[i+1]--;} //不够减向上一位借个1 是不是很形象 c[i] = a[i] - b[i]; //将计算结果输入保存结果的数字中 i++; } // 默认lena >= lenb while( i <= lena ) { //如果数字a位数很多，数字b位数比他少，那么上一步结束后i == lenb 还有一些未处理的数字在数组a中 if(a[i] < 0) {a[i] += 10; a[i+1]--;} //这一步就是对这些数字进行操作 c[i] = a[i]; } // 上一步结束后 i == lena 但是次数可能会有前导0，下一步就是把前导零删除 while(!c[i] && i > 1) i--; for(int j = i; j >= 1; j--) printf("%d",c[j]); //倒序输出，为什么要倒序呢？还记不记得上面你已经倒序了一次，这回就是给他正过来 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
- 45
- 46
- 47
- 48
4 小数形式与科学计数法转换（简）
【问题描述】
编写一个程序，将用小数表示的浮点数，转换成科学计数法的形式输出。输入的数据没有符号，小数点前后必有数字，且全为有效数据，即小数点后的末尾数字不为0；小数点前若只有一位数字，可以为0，否则小数点前的最高位数字不为0。
提示：以字符串形式保存相关数据。
【输入形式】
从控制台输入一小数，最后有回车换行符，所有输入的字符数不会超过100。
【输出形式】
以科学计数法形式输出数据。输出的数据由以下几部分构成：
1.底数部分是一个小数或整数，若为小数，则小数点前后必有数字，而且都为有效数字。即：小数点前只有一位大于0的数字，小数点后的末尾数字不能为0。若为整数，则只有一位数字，不带小数点。
2.必有小写字母“e”。
3.指数部分是一个整数，若大于等于0，则不带正号“+”。若小于0，则需要带负号“-”，且整数的最高位数字不为0。
【输入样例1】
0.000000000000002
【输出样例1】
2e-15
【输入样例2】
8.9845623489651700659
【输出样例2】
8.9845623489651700659e0
【输入样例3】
367298599999093453490394859509568659795603.4
【输出样例3】
3.672985999990934534903948595095686597956034e41
【样例说明】
以小数形式输入数据，然后转换成科学计数法形式输出。
【评分标准】
该题要求以科学计数法形式输出数据，提交程序文件名为notation.c。
思路：
谔，这个题也不难，也是模拟就能做的题。。。不多讲了
题解：
#include <stdio.h> #include <string.h> char s[105]; //s用来存读入的数字 int num[105]; int main() { int wei=0,i,flag = 0,zf = 0,fcnt = 0,k = 0; scanf("%s",s); //读入数字 for(i = 0; i< strlen(s);i++) { if(s[i] == '.') flag = 1; //出现小数点了，标记一下 if(flag == 1) wei++; //小数点后的数字，小数位数 if(s[0]=='-') zf = -1; //如果是负数，记录一下 if(s[i] != '0' && s[i] != '-' && s[i] != '.') fcnt = 1; //发现第一个非零数，标记一下 可能有0.0000123的情况 if(fcnt == 1 && s[i] != '.') num[k++] = s[i] - '0'; //读入非零数 非零数的个数为K } wei--; if(zf == -1) printf("-"); //是负数 for(i = 0; i< k;i++) { if(i==1) printf(".%d",num[i]); //科学技术法的形式，整数位只有一个数 else printf("%d",num[i]); } int zhishu = k - 1 - wei; //指数就等于总共的非零数的个数 - 小数点后的位数 - 1 printf("e%d",zhishu); //输出指数 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
5 全排列数的生成
【问题描述】输入整数N( 1 <= N <= 10 )，生成从1~N所有整数的全排列。
【输入形式】输入整数N。
【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。
【样例输入1】1
【样例输出1】1
【样例说明1】输入整数N=1，其全排列只有一种。
【样例输入2】3
【样例输出2】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【样例说明2】输入整数N=3，要求整数1、2、3的所有全排列, 共有N!=6行。且先输出1开头的所有排列数，再输出2开头的所有排列数，最后输出3开头的所有排列数。在以1开头的所有全排列中同样遵循此原则。
【样例输入3】10
【样例输出3】
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 9 8 10
1 2 3 4 5 6 7 9 10 8
1 2 3 4 5 6 7 10 8 9
1 2 3 4 5 6 7 10 9 8
1 2 3 4 5 6 8 7 9 10
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 8 9 7 10
1 2 3 4 5 6 8 9 10 7
……………………
【样例说明3】输入整数N=10，要求整数1、2、3、……、10的所有全排列。上例显示了输出的前10行。
【运行时限】要求每次运行时间限制在20秒之内。超出该时间则认为程序错误。提示：当N增大时，运行时间将急剧增加。在编程时要注意尽量优化算法，提高运行效率。
【评分标准】该题要求输出若干行整数。。
思路：
这个题比较有意思，用到了dfs的搜索的思路，很简单的dfs，也不想说了。。。。。 别怪我懒，了解一点dfs就能做。
题解：
#include<stdio.h> int a[10],book[10]={0}; int n; void dfs(int step) { int i; if(step==n){ for(i=0;i<n;i++){ printf("%d ",a[i]); } printf("\n"); return; } for(i=0;i<n;i++){ if(book[i]==0){ //第i个数还没有用过 a[step]=i+1; book[i]=1; //标记第i个数，表示已经用过 dfs(step+1); book[i]=0; //解除第i个数的标记 } } } int main(){ scanf("%d",&n); dfs(0); 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
