本系列文章將于2021年整理出版，書名《演算法競賽專題決議》，
前驅教材：《演算法競賽入門到進階》 清華大學出版社
網購：京東 當當 ??? ?作者簽名書
如有建議，請加QQ 群：567554289，或聯系作者QQ：15512356
文章目錄
- C.1 計算大數
- C.2 構造亂數和隨機字串
- C.3 陣列去重
- C.4 構造測驗資料和對拍
??很多人認為Python是最受歡迎的編程語言，它編碼簡潔，有強大的庫，
??Python早已應用在演算法競賽中，能節省大量比賽時間，
??大學的某些演算法競賽（ICPC）已經支持用Python語言提交代碼，即使比賽不支持用Python提交代碼，而Linux系統一般是預裝Python的，可以用Python做輔助作業，
??Python的優點有編碼簡便、處理大數非常簡單、構造測驗資料比C++更簡單等，Python的主要問題是執行時間慢，比C++、java慢得多，競賽隊員可能不會直接用Python交題，不過，Python可以作為工具使用，常用的是構造資料、寫對拍代碼，一個典型的應用是：如果能用打表法交題，可以先用python打表出資料，然后用c++或直接用Python提交，
??讀者會發現，用Python做這些事，比用C++容易得多，這在緊張的比賽中是很有用的，
??若讀者想學習用Python寫演算法競賽題的代碼，建議到力扣網站（leetcode-cn.com）練習，每個題都有人提交Python題解，
??Python的強大，主要是因為它龐大的庫，Python有兩種版本Python 2、Python 3，兩者不兼容，本節基于 Python 3，Python編譯環境下載地址：https://www.python.org/downloads/
??下面介紹Python在演算法競賽中的應用，
C.1 計算大數
??下面的題目是計算大數，
階乘之和 洛谷 P1009https://www.luogu.com.cn/problem/P1009
題目描述：計算S=1!+2!+3!..+n! (n≤50)
??計算結果是一個天文數字，如果用C++編碼，需要用高精度，很復雜，而Java和python都能直接處理大數，
??用Java編碼很簡單：
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in= new Scanner(System.in);
int n = in.nextInt();
BigInteger s = new BigInteger("1");
BigInteger ans = new BigInteger("0");
for (int i = 1; i <= n; i++) {
s = s.multiply(new BigInteger(String.valueOf(i)));
ans = ans.add(s);
}
System.out.println(ans);
}
}
??用Python編碼更簡單：
n = int(input())
s = 1
ans = 0
for i in range(1,n+1,1):
s *= i
ans += s
print(ans)
C.2 構造亂數和隨機字串
??用Python構造測驗資料，比c++簡單得多，它能直接產生極大的數字，方便地產生隨機字符等，下表列出了一些典型的亂數、隨機字串構造方法1，
（1）匯入庫
import random
??可以寫成：
from random import *
??此時后面的代碼能夠簡單一點，例如把random.randint直接寫為randint
（2）在指定范圍內生成一個很大的隨機整數：
print (random.randint(-9999999999999999,9999999999999999))
??輸出示例：428893995939258
（3）在指定范圍內（0到100000）生成一個隨機偶數：
print (random.randrange(0, 100001, 2))
??輸出示例：14908
（4）生成一個0到1之間的隨機浮點數：
print (random.random())
??輸出示例：0.2856636141181378
（5）在指定范圍內（1到20）生成一個隨機浮點數：
print (random.uniform(1, 20))
??輸出示例：9.81984258258233
（6）在指定字符中生成一個隨機字符：
print (random.choice('abcdefghijklmnopqrst@#$%^&*()'))
??輸出示例：D
（7）在指定字符中生成指定數量的隨機字符：
print (random.sample('zyxwvutsrqponmlkjihgfedcba',5))
??輸出示例：[‘z’, ‘u’, ‘x’, ‘w’, ‘j’]
（8）匯入庫
import string
??若寫成from string import *，下面的string.ascii_letters改為ascii_letters
（9）用a-z、A-Z、0-9生成指定數量的隨機字串：
ran_str = ''.join(random.sample(string.ascii_letters + string.digits, 8))
print (ran_str)
??輸出示例：iCTm6yxN
（10）從多個字符中選取指定數量的字符組成新字串：
print (''.join(random.sample(['m','l','k','j','i','h','g','d'], 5)))
??輸出示例：mjlhd
（11）打亂陣列的順序：
items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
random.shuffle(items)
for i in range(0,len(items),1): #逐個列印
print (items[i]," ",end='')
??輸出示例：1 0 8 3 5 7 9 4 6 2
C.3 陣列去重
??下面給出兩種方法：第1種方法用set()，速度很快，它的復雜度是O(1)的；第2種方法是暴力去重，非常慢，
def NonRepeatList1(data): #函式1：set去重，不保持原順序
return list(set(data))
def NonRepeatList2(data): #函式2：暴力去重，保持原順序
return [i for n, i in enumerate(data) if i not in data[:n]]
#下面測驗上面2個函式
import random
import time
time0=time.time()
a = []
for i in range(0,100000,1): #10萬個亂數
a.append(random.randint(0,20))
#print (a) #可以列印陣列看看
print ("random time=",time.time()-time0) #列印時間
time0 = time.time()
b = NonRepeatList1(a) #去重，不保持原順序
#print (b) #列印看看是否亂序
print ("set time=",time.time()-time0)
time0 = time.time()
c = NonRepeatList2(a) #去重，保持原順序
#print (c) #列印看看是否保持原序
print ("enum time=",time.time()-time0)
??代碼中統計了兩種方法的執行時間，在作者的電腦上運行，輸出時間是：
random time= 0.0957651138305664
set time= 0.000997781753540039
enum time= 13.196359395980835
C.4 構造測驗資料和對拍
??仍然以Hdu 1425為例，
hdu 1425 sort http://acm.hdu.edu.cn/showproblem.php?pid=1425
給你n個整數，請按從大到小的順序輸出其中前m大的數，
輸入：每組測驗資料有兩行，第一行有兩個數n, m(0 < n, m < 1000000)，第二行包含n個各不相同，且都處于區間[-500000, 500000]的整數，
輸出：對每組測驗資料按從大到小的順序輸出前m大的數，
??首先構造測驗資料，下面的代碼生成60多萬個不同的無序的亂數，首先產生100萬個亂數，然后用set去重，最后用shuffle打亂即可，
#設本代碼的檔案名是aa.py
import random
a= []
b= []
for i in range(0,1000000,1): #100萬個亂數
a.append(random.randint(-500000,500000))
b=list(set(a)) #去重
#print("lena=",len(a)) #驗證a的個數是不是100萬個
#print("lenb=",len(b)) #b的個數有60多萬個
random.shuffle(b) #打亂b
print(len(b),random.randint(1,len(b))) #列印n、m
for i in range(0,len(b),1): #逐個列印
print ( b[i],end=' ')
#下面的做法是存到一個檔案里面，其實不需要
'''
f = open("d:\data.in", "w") #輸出到檔案里
print(len(b),random.randint(1,len(b)),file=f)
for i in range(0,len(b),1): #逐個列印
print ( b[i],end=' ',file=f)
f.close()
'''
??下面以Windows環境為例說明構造測驗資料和對拍的程序，linux環境類似，
??把上面的代碼存為檔案aa.py，執行下面的命令，輸出測驗資料到檔案data.in
D:\>C:\Users\hp\AppData\Local\Programs\Python\Python39\python aa.py >data.in
??作者的python安裝在目錄“C:\Users\hp\AppData\Local\Programs\Python\Python39\”，讀者可以按自己的目錄操作，或者設定環境變數，就不用輸這個目錄了，
??下面給出Hdu 1425的對拍代碼，功能是：先輸入n和m，然后輸入n個數，排序后，列印出前m大的數，與C++對拍代碼相比，Python代碼更簡單，
#設本代碼的檔案名是bb.py
n,m = map(int,input().split()) #輸入n、m
a=[int(n) for n in input().split()] #輸入n個數
a.sort() #排序
for i in range(n-1,n-m,-1): #列印出前m-1大的數
print ( a[i],end=' ')
print ( a[n-m]) #列印出第m大的數
??把代碼存為檔案bb.py，Windows環境下，執行以下命令，讀輸入資料data.in，輸出資料到py.out
D:\>C:\Users\hp\AppData\Local\Programs\Python\Python39\python bb.py <data.in >py.out
??前一節“測驗資料的構造與對拍https://blog.csdn.net/weixin_43914593/article/details/106863166”的hash代碼是：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int a[MAXN];
int main(){
int n,m;
while(~scanf("%d%d", &n, &m)){
memset(a, 0, sizeof(a));
for(int i=0; i<n; i++){
int t;
scanf("%d", &t); //此題資料多，如果用很慢的cin輸入，肯定TLE
a[500000+t]=1; //數字t，登記在500000+t這個位置
}
for(int i=MAXN; m>0; i--)
if(a[i]){
if(m>1) printf("%d ", i-500000);
else printf("%d\n", i-500000);
m--;
}
}
return 0;
}
??設代碼的檔案名是hash，執行代碼，讀取輸入data.in，輸出到檔案hash.out
D:\>hash <data.in >hash.out
??下面比較2個代碼的輸出是否一樣，執行以下命令：
D:\>fc py.out hash.out /n
??Linux環境下是diff命令
[root]#diff -c hash.out py.out
參考https://www.cnblogs.com/zqifa/p/python-random-1.html ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/237120.html
標籤：其他
上一篇：Educational Codeforces Round 100 A—D題題解
下一篇：Spring 原始碼詳解(一)