网站制作代理平台,大连工业大学研究生,襄阳网站建设品牌,去成都旅游攻略报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周#xff08;读者可以按…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周读者可以按自己的进度选“正常”和“快进”两种计划。 每周3次集中答疑周三、周五、周日晚上在QQ群上答疑 文章目录 1. 数组的应用--高精度1.1 Java和Python计算大数1.2 C/C高精度计算大数1.2.1 高精度加法1.2.2 高精度减法1.2.3 高精度乘法1.2.4 高精度除法 2. 队列2.1 手写队列2.1.1 C/C手写队列2.1.2 Java手写队列2.1.3 Python手写队列 2.2 C STL队列queue 2.3 Java队列Queue 2.4 Python队列Queue和deque2.5 例题2.5.1 C/C代码2.5.2 Java代码2.5.3 Python 3. 习题 第 6周: 高精度、队列
1. 数组的应用–高精度 高精度算法就是大数的计算方法。超过64位的大数计算Java和Python都能直接算而C不能直接算需要用数组来模拟大数的存储。 竞赛中常常用到很大的数组。强烈建议不要用动态分配因为动态分配需要多写代码而且容易出错。定义为全局静态数组即可而且不需要初始化为0因为全局变量在编译时会自动初始化为全0。
#include bits/stdc.h
using namespace std;
int a[10000000]; //定义一个很大的全局数组。自动初始化为0不需要写成int a[10000000]{0};
int main(){cout a[0]; //输出0return 0;
}大数组不能定义在函数内部这样做会导致栈溢出。因为局部变量是函数用到时才分配大小不能超过栈而栈不会很大。 这样写是错的
#include bits/stdc.h
using namespace std;
int main(){int a[10000000]{0}; //这样写是错的大数组不能定义在函数内部cout a[0]; //出错return 0;
}另外注意全局变量和局部变量的初值。全局变量如果没有赋值在编译时被自动初始化为0。在函数内部定义的局部变量若需要初值为0一定要初始化为0否则可能为莫名其妙的值。
#include bits/stdc.h
using namespace std;
int a; //全局变量自动初始化为0
int c 999; //赋值为999
int main(){int b;cout a endl; //输出0cout c endl; //输出999cout b endl; //由于b没有初始化这里输出莫名奇妙的值return 0;
}1.1 Java和Python计算大数 Java和Python计算大数理论上可以计算“无限大”的数只要不超内存。 用下面的简单题说明Java和Python的大数计算。 【题目描述】 大数计算输入两行表示两个整数。分别计算加、减、乘、除分5行输出和、差、积、商、余数。 1Java代码。注意负数的计算负数的加减乘都没问题但是除法可能出错。
import java.math.BigInteger;
import java.util.Scanner;
public class Main { public static void main(String[] args) {Scanner scnew Scanner(System.in);BigInteger a,b;asc.nextBigInteger(); bsc.nextBigInteger(); System.out.println(a.add(b)); System.out.println(a.subtract(b)); System.out.println(a.multiply(b)); System.out.println(a.divide(b)); System.out.println(a.mod(b)); //注意如果b是负数这里可能报错}
}2Python代码。注意负数的计算加减乘都没问题但是除法的结果可能比较奇怪。
aint(input())
bint(input())
print(ab)
print(a-b)
print(a*b)
print(a // b) #注意如果a或b是负数除法的结果可能比较怪例如123//(-10)得-13
print(a % b) #注意如果a或b是负数求余的结果可能比较怪例如123%(-10) 得-71.2 C/C高精度计算大数 C能表示的最大整数是64位的long long如果需要计算更大的数需要使用“高精度”。对于加减乘除四种计算模拟每一位的计算并处理进位或借位。 1数字的读取和存储。因为整数a和b太大无法直接赋值给C的变量不能按数字读入只能按字符读入。大数a用字符串string读入一个字符存一位数字。注意存储的顺序读入的时候数字的左边是高位右边是低位即a[0]是最高位a[n-1]是最低位但是计算时习惯用a[0]表示最低位a[n-1]表示最高位所以需要把输入的字符串倒过来。 2加法和减法。简单地模拟即可。 3乘法。模拟小学竖式乘法操作例如34×67计算过程 计算结果用int a[]存储首先算出a[0]4×728a[1]3×74×62124a[2]3×618然后处理进位得到乘积2278。 4除法。直接做除法有点麻烦简单一点的方法是利用减法。例如a除以b转化为a连续减去b减了多少次就是商最后不够减的是余数。
1.2.1 高精度加法 链接大整数加法 把输入的数字存到字符串中然后在add()中把字符转成数字做完加法后再转回字符。
#includebits/stdc.h
using namespace std;
int na[1005],nb[1005]; //加数和被加数
string add(string a,string b){int lenaa.size(),lenbb.size();for(int i0;ilena;i)na[lena-1-i] a[i]-0; //把字符转成数字然后翻转使na[0]是最低位for(int i0;ilenb;i)nb[lenb-1-i] b[i]-0;int lmax lenalenb ? lena : lenb;for(int i0;ilmax;i) {na[i] nb[i];na[i1] na[i]/10; //处理进位na[i]%10;}if(na[lmax]) lmax; //若最高位相加后也有进位数字长度加1string ans;for(int ilmax-1;i0;i--) //把数字转成字符然后翻转ans na[i]0;return ans;
}
int main(){string a,b;cin a b;cout add(a,b);return 0;
}1.2.2 高精度减法 链接大整数减法
#includebits/stdc.h
using namespace std;
int na[1005],nb[1005]; //被减数和减数
string sub(string a,string b){if(a b) return 0; //特判一下是否两数字相等bool neg 0; //标记是否为负数if(a.size() b.size() || a.size() b.size() a b)swap(a, b), neg 1; //让a大于bint lenaa.size(),lenbb.size();for(int i0;ilena;i) //把字符转成数字然后翻转使na[0]是最低位na[lena-1-i]a[i]-0;for(int i0;ilenb;i)nb[lenb-1-i]b[i]-0;int lmax lena;for(int i0;ilmax;i){na[i] - nb[i];if(na[i]0){ //处理借位na[i]10;na[i1]--;}}while(!na[--lmax] lmax0) //找到首位为0的位置; //什么都不做lmax;string ans;for(int ilmax-1;i0;i--) //把数字转成字符然后翻转ans na[i]0;if(neg) ans - ans; //查询一下是否为负数return ans;
}
int main(){string a,b;cinab;coutsub(a,b);return 0;
}1.2.3 高精度乘法 链接大整数乘法
#includebits/stdc.h
using namespace std;
int na[1005], nb[1005], nc[1000005];
string mul(string a,string b){if(a0||b0) return 0;int lenaa.size(),lenbb.size();for(int i0;ilena;i)na[lena-i]a[i]-0;for(int i0;ilenb;i)nb[lenb-i]b[i]-0;for(int i1;ilena;i)for(int j1;jlenb;j)nc[ij-1] na[i]*nb[j];for(int i1;ilenalenb;i)nc[i1]nc[i]/10,nc[i]%10;string ans;if(nc[lenalenb]) ans nc[lenalenb]0;for(int ilenalenb-1;i1;i--) ans nc[i]0;return ans;
}
int main(){string a,b;cinab;coutmul(a,b);return 0;
}1.2.4 高精度除法 链接大整数除法
#includebits/stdc.h
using namespace std;
string sub(string a,string b){//模拟大整数减法 string res;int na.size(),mb.size(),i,by1;reverse(a.begin(),a.end());reverse(b.begin(),b.end());for(i0;im;i){int ta[i]-b[i]9by;rest%100;byt/10;}for(;in;i){int ta[i]-09by;rest%100;byt/10;}//消去前缀零 while(res[--i]0i0);resres.substr(0,i1);reverse(res.begin(),res.end());return res;
}
int main(){string s1,s2,res,ans;cins1s2;bool hfalse;int ns1.size(),ms2.size(),t;//查找被除数末端非零位 int fn-1;while(s1[f]0)f--;//模拟除法 for(int i0;in;i){//遍历被除数 anss1[i];t0;while(ans.size()m||ans.size()manss2){//具体操作 anssub(ans,s2);//用减法模拟除法 t;} if(t||h){//等待商的首位 htrue;rest0;}if(ans.empty()if){//处理后缀零 while(in)res0; }}if(res.empty())res0;//余数为零 if(ans.empty())ans0;//商为零 coutresendlans;return 0;
} 2. 队列 队列中的数据存取方式是“先进先出”只能往队尾插入数据、从队头移出数据。队列的原型在生活中很常见例如食堂打饭的队伍先到先服务不能插队。 下图是队列的原理队头head指向队列中的第一个元素 a 1 a_1 a1队尾tail指向队尾最后一个元素 a n a_n an。元素只能从队头方向出去元素只能从队尾进入队列。
2.1 手写队列
2.1.1 C/C手写队列 队列的代码很容易实现。如果使用环境简单最简单的手写队列代码用数组实现。
const int N 10000; //定义队列容量确保够用
int que[N]; //队列用数组模拟
int head 0; //head始终指向队头。que[head]是队头。开始时队列为空head 0
int tail -1; //tail始终指向队尾。que[tail]是队尾。开始时队列为空tail -1//队列长度等于tail-head1
head; //弹出队头元素让head指向新队头。注意保持head tail
que[head]; //读队头
que[tail] data; //入队先tail加1然后数据data入队。注意tail必须小于N这个手写代码有一个严重缺陷如果进入队列的数据太多使得tail超过了N数组que[N]就会溢出导致出错。 用下面的例子给出上述手写代码的应用。 约瑟夫问题 https://www.luogu.com.cn/problem/P1996 约瑟夫问题是一个经典问题可以用队列、链表等数据结构实现。下面的代码用队列来模拟报数。如果不理解代码可以模拟执行的过程。
#include bits/stdc.h
using namespace std;
const int N 10000; //定义队列大小确保够用
int que[N];
int head0, tail-1;
int main(){int n,m;cinnm;for(int i1;in;i) que[tail] i;while((tail-head1)!0){for(int i1;im;i){que[tail] que[head];head;}cout que[head] ;head;}coutendl;return 0;
}代码第3行定义了队列的容量N 10000。本题的n最大是100每人出圈一次所以队列长度一定不超过100×100。如果把N设置小了例如N2000提交到OJ会返回RE即Runtime Error说明溢出了。 如果要防止溢出可以使用循环队列。在上面例子中只需要设置一个N100的循环队列即可。 手写循环队列的代码见《算法竞赛》第8页“1.2.2 手写循环队列”。 队列是一种线性数据结构线性数据结构的主要缺点是查找较慢。要在队列中查找某个元素只能从头到尾一个个查找。
2.1.2 Java手写队列 下面是Java的手写队列代码和C代码基本一样。
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int[] que new int[10000]; // 定义队列大小确保够用int head 0, tail -1;for (int i 1; i n; i) que[tail] i; while ((tail - head 1) ! 0) {for (int i 1; i m; i) {que[tail] que[head];head;}System.out.print(que[head] );head;}System.out.println();}
}2.1.3 Python手写队列 下面是Python的手写队列代码。这个手写队列是用list实现的进队尾用append()实现队列自动扩展不会有溢出问题。
n, m map(int, input().split())
que [i for i in range(1, n1)]
head, tail 0, n-1 #队头和队尾
while tail - head 1 ! 0:for i in range(1, m):que.append(que[head])head 1tail 1print(que[head], end )head 12.2 C STL队列queue CSTL官方文档英文主页 https://en.cppreference.com/或中文主页https://zh.cppreference.com/ queue的文档https://en.cppreference.com/w/cpp/container/queue 竞赛时一般不自己手写队列而是用STL queue而且没有溢出的问题大大加快了做题速度。STL queue的主要操作见下表。 这里有篇博文可以参考STL queue 下面是 约瑟夫问题 的STL queue实现。
#include bits/stdc.h
using namespace std;
int main(){int n,m;cinnm;queueintq;for(int i1;in;i) q.push(i);while(!q.empty()){for(int i1;im;i){q.push(q.front());q.pop();}cout q.front() ;q.pop();}coutendl;return 0;
}2.3 Java队列Queue Java官方文档https://docs.oracle.com/en/java/ Queue的文档https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/Queue.html Java用LinkedList实现基本队列Queue。常用操作有 这篇博文可以参考Java队列 下面是 约瑟夫问题 的Java Queue实现。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();QueueInteger q new LinkedList();for (int i 1; i n; i) q.offer(i);while (!q.isEmpty()) {for (int i 1; i m; i) {q.offer(q.peek());q.poll();}System.out.print(q.peek() );q.poll();}}
}2.4 Python队列Queue和deque Python官方文档https://docs.python.org/3/ deque文档https://docs.python.org/3/library/collections.html#collections.deque Python的队列可以用list、Queue、deque实现。 下面先用Queue实现 约瑟夫问题 。
from queue import Queue
n, m map(int, input().split())
q Queue()
for i in range(1, n1): q.put(i)
while not q.empty():for i in range(1, m): q.put(q.get())print(q.get(), end )不过建议算法竞赛只使用deque不要用queue。算法竞赛的代码都是单线程的在这种场景下deque比Queue快很多。 deque是双向队列队头和队尾都能插入和弹出。当成普通队列使用时只用它的队头弹出、队尾插入功能即可。deque的常用操作有 参考博文Deque 下面用deque实现 约瑟夫问题 。
from collections import deque
n, m map(int, input().split())
dq deque(range(1, n1))
while dq:dq.rotate(-(m-1)) #把前m-1个数挪到队列尾部print(dq.popleft(), end ) #队头是第m个数删除并打印它。2.5 例题 机器翻译 用一个哈希表hashtable[]模拟内存若hashtable[x]true表示x在内存中否则不在内存中。用队列queue对输入的单词排队当内存超过M时删除队头的单词。
2.5.1 C/C代码
#include bits/stdc.h
using namespace std;
bool hashtable[1003]; //全局数组自动初始化为0
int main(){int m,n;cin m n;int ans0; //函数内部变量一定要初始化为0queueint q;for(int i0;in;i) {int x; cin x;if(hashtable[x] false) {hashtable[x] true;if(q.size() m) q.push(x);else {hashtable[q.front()] false;q.pop();q.push(x);}ans; //内存中没有这个单词到外存找答案加1}}cout ans \n;return 0;
}2.5.2 Java代码
import java.util.*;
public class Main {static boolean[] hashtable new boolean[1003];static QueueInteger q new LinkedList(); //使用LinkedList实现队列public static void main(String[] args) {int m, n;Scanner scanner new Scanner(System.in);m scanner.nextInt();n scanner.nextInt();int ans0;for (int i 0; i n; i) {int x scanner.nextInt();if (hashtable[x] false) {hashtable[x] true;if (q.size() m)q.add(x); //使用add方法添加元素到队列中else {//int front ; //使用poll方法取出队列头部元素并移除hashtable[q.poll()] false;q.add(x);}ans;}}System.out.println(ans);}
}2.5.3 Python
from collections import deque
hashtable [False] * 1003 # 哈希表初始化默认为False
m, n map(int, input().split()) # 输入m和n
ans 0 # 初始化答案为0
q deque() # 初始化队列
line list(map(int, input().split())) #读第2行
for x in line: #处理每个数 if hashtable[x] is False: # 如果x不在哈希表中 hashtable[x] True # 将x加入哈希表 if len(q) m: # 如果队列未满 q.append(x) # 将x加入队列 else: # 如果队列已满 hashtable[q.popleft()] False # 将队列首元素出队并从哈希表中删除 q.append(x) # 将x加入队列 ans 1 # 答案加1
print(ans) # 输出答案
3. 习题
https://www.lanqiao.cn/problems/3745/learning/ https://www.lanqiao.cn/problems/3746/learning/
