谈谈Python与OI相关的简单运用

· · 个人记录

Python简介

Python是工程设计中的一种常用语言。它因为功能强大、代码简洁而深受程序猿喜爱。

Python有着许多优秀的特性，有时对我们的解题有很大的帮助。恰好，NOI考场上提供的NOI Linux也自带了Python，因此，谁也无法阻挡我们用Python去干一些奇怪事情。相信学会Python，在考场上会为你的解题提供另一种思路。当然，就算考场上不用到它，我们也可以用它来使我们的算法程序摆脱控制台，变得更加美观。

下面，我就简单地介绍Python的3个与OI相关的应用

高精度

不知道大家有没有做过[FJOI2007]轮状病毒那道题

这题的结论就是已知f(1)=1，f(2)=5，要求数列f(x)=3f(x-1)-f(x-2)+2，的第n项。但是答案很大，一定会爆long long

这时候使用C++就变得异常头疼。我相信不只我一个人非常厌烦高精度吧。那假如你在考场，你会怎么做呢？

写高精度？那非常浪费时间，除非你对高精度模板非常熟悉。但很多选手早已经忘记了入门时期学的这个鬼东西，自己模拟着写一遍，又很难调试。但假如你有一门自带高精度的语言？

你需要Python!

Python自带高精度，虽然正式比赛中不允许提交Python代码，但这题的输入只有100种可能，因此我们可以用Python打表！

上图的左边是简短的Python代码，而右边是按C++的语法打出的表。于是我们可以把打出的表直接复制，并存为C++代码，然后稍作修改，提交这个C++代码，就可以AC了！相比起花15分钟写个高精度，这样是不是划算很多？2分钟AC一道省选题！

贴上代码，大家试试吧！

for n in range(3,101):
    a=1
    b=5
    for i in range(3,n+1)
        c=3*b-a+2
        a=b
        b=c
    print("if(n==)",n,")puts(\"",c,"\");")

随机数

众所周知，C++的随机数依赖于“秒”这一时间单位而存在（前提是你不搞什么奇技淫巧）。因此，对拍时就会有弊端，1分钟只能拍60组数据，效率非常低，等真正拍出问题来了，早已经没有反应时间了

你需要Python!

Python的随机数，比C++更加随机，它并不依赖于“秒”，具体依赖于什么我也不太清楚，但比C++的随机效率更高

最重要的是代码非常简短！甚至根本不用进行C++的srand()这一过程！

生成一个1~10000的随机数，只要两行代码：

import random
print(int(random.uniform(1,10001)))

而C++却需要整整6行：

#include<bits/stdc++.h>
using namespace std;
int main(){
    srand(time(0));
    printf("%d\n",rand()%10000+1);
}

而且C++的rand模上一个数，区间内的数并不是等概率生成的。rand()的范围是32767，模上10000之后，显然2767以内的数出现概率高于其它数。Python根本不用担心这个问题！

做窗口

C++也可以做窗口，但是需要一段冗长的初始化代码，不便于记忆，而且提供的接口也并不容易使用，经常会出现兼容性问题。那如果我写了一个自我感觉不错的算法，我要怎么展示给用户呢？用控制台是肯定不被用户接受的。

你需要Python!

举一个具体的例子：拉格朗日插值。用户输入一些点坐标，以及一个待插值的x，你需要计算f(x)

先给一个效果图：

窗口界面需要引入tkinter库。这个库给我们提供了窗口所需的各种操作。以下是我们需要用到的一些窗口函数：

这些函数的具体用法，可以参见下面的代码。初学者可以copy下面的代码，对它进行膜改，做一个自己的窗口程序。如果不知道怎么膜改，或者膜改过程中有什么疑问，欢迎来骚扰我！（当然，最好在NOI比赛结束之后再骚扰）

from tkinter import *
import tkinter.messagebox as messagebox
from tkinter import ttk

def lagrange(arrx,arry,n,x):
    ans=0
    for i in range(0,n):
        s1=1
        s2=1
        for j in range(0,n):
            if i==j: continue
            s1=s1*(x-arrx[j])
            s2=s2*(arrx[i]-arrx[j])
        ans=ans+s1/s2*arry[i]
    return ans

class Application(Frame):
    def __init__(self, master=None):
        Frame.__init__(self, master)
        self.pack()
        self.createWidgets()

    def createWidgets(self):
        self.tipx = ttk.Label(self, text='各点的x值：')
        self.tipx.pack()
        self.arrxInput = Entry(self)
        self.arrxInput.pack()
        self.tipy = ttk.Label(self, text='各点的y值：')
        self.tipy.pack()
        self.arryInput = Entry(self)
        self.arryInput.pack()
        self.tipxx = ttk.Label(self, text='您需要插的x值：')
        self.tipxx.pack()
        self.xInput = Entry(self)
        self.xInput.pack()
        self.alertButton = Button(self, text='Lagrange', command=self.calc)
        self.alertButton.pack()

    def calc(self):
        arrxin = self.arrxInput.get()
        arryin = self.arryInput.get()
        xin = int(self.xInput.get())
        sarrx = arrxin.split()
        sarry = arryin.split()
        arrx = []
        arry = []
        n=0
        for i in sarrx:
            arrx.append(int(i))
            n=n+1
        for i in sarry:
            arry.append(int(i))
        res = lagrange(arrx,arry,n,xin)
        messagebox.showinfo('Result', '%d' % res)

app = Application()
app.master.geometry("200x180")
app.master.title('Lagrange!')
app.mainloop()

写在最后的广告

蒟蒻的博客：Ebola的OI笔记