scturtle's 渣代码集散地

二分查找第一次出现的位置

2011年3月17日 15:58

这个简单的问题以前居然没有想过,今天看书才发现二分也是可以做的,顺便用刚学的random库验证一下

# coding: utf-8
from random import *

def first(a,x):
    try:
        return a.index(x)
    except ValueError:
        return -1

def firstbin(a,x):
    l=0; u=len(a)-1
    while True:
        if l>u:
            return -1
        m=(l+u)/2
        if a[l]==x:
            return l
        elif a[m]<x:
            l=m+1
        elif a[m]==x:
            u=m
        elif a[m]>x:
            u=m-1

if __name__ == '__main__':
    cishu=1
    while True:
        a=[]
        for i in range(randint(1,10)):
            a.extend(range(100))
        a=sample(a,randint(0,len(a)))
        a.sort()
        x=randint(0,99)
        print cishu,
        cishu+=1
        if first(a,x)==firstbin(a,x):
            print 'OK'
            #print x,a
        else:
            print 'OOH!'
            print a,x
            break

update:

编程珠玑(中文第2版)88-90页上给出的另两种:

def binsearch(a,x):
    l=-1;u=len(a)
    while l+1!=u:
        # invariant: x[l]<t && x[u]>=t && l<u
        m=(l+u)/2
        if a[m]<x:
            l=m
        else:
            u=m
    # assert: l+1=u && x[l]<t && x[u]>=t
    p=u
    if p>=len(a) or a[p]!=x:
        p=-1
    return p

def binsearch(a,x):
    if len(a)==0:
        return -1
    i=max1(len(a))
    print len(a),i
    l=-1
    if a[i-1]<x:
        l=len(a)-i
    while i!=1:
        # invariant: x[l]<t && x[l+i]>=t && i=2^j
        i=i/2
        if a[l+i]<x:
            l=l+i
    # assert: i==1 && x[l]<t && x[l+i]>=t
    p=l+1
    print p
    if p>=len(a) or a[p]!=x:
        p=-1
    return p

循环不变式断言和脚手架是好东西

书上说第二个的循环展开非常经典高效

评论(0) 阅读(1988)

mingw opengl 环境配置笔记

2011年3月05日 11:37

下载这个库文件,glut.h放到 C:\MinGW32\include\GL 下面,glut32.dll和glut32.lib放到工程目录下.

编写makefile:

CC = gcc
CFLAGS = -Wall -g
LIBS = -lopengl32 -lglu32
main.exe : main.c
	$(CC) $(CFLAGS) -o main.exe main.c glut32.lib $(LIBS)
clean:
	rm main.exe

为了能在gvim中执行make,要么在gvim中:set makeprg=mingw32-make 要么安装msys并将可执行目录加到系统path环境变量中.

glaux待研究...

update:

顺便记录一下archlinux下的配置:

安装 freeglut mesa 这两个包.

makefile写成:

CC = gcc
CFLAGS = -Wall -g
LIBS = -lglut -lGL -lGLU -lm -L/usr/X11R6/lib
test: test.c
	$(CC) $(CFLAGS) -o test test.c $(LIBS)
clean:
	rm test

update2:

http://www.martinpayne.me.uk/software/development/GLUT/ 有编译好的win平台的freeglut,glut包

参考:

https://users.cs.jmu.edu/bernstdh/web/common/help/cpp_mingw-glut-setup.php

http://blog.csdn.net/halechan/archive/2010/07/18/5744023.aspx

http://tieba.baidu.com/f?kz=757588649

评论(2) 阅读(7863)

zip my comics

2011年2月28日 09:57

# coding: utf-8
import os,sys,zipfile

def walkdir(d):
    l=os.listdir(d)
    nodir=True
    for t in l:
        p=os.path.join(d,t)
        if os.path.isdir(p):
            nodir=False
            walkdir(p)
    if nodir:
        fn=d+'.zip'
        if os.path.exists(fn):
            print 'Skip:',os.path.basename(fn)
            return
        z=zipfile.ZipFile(fn,'w')
        print 'Get:',os.path.basename(fn)
        for t in l:
            p=os.path.join(d,t)
            z.write(p,t)
        z.close()

if __name__ == '__main__':
    walkdir(os.path.abspath('.'))
    t=raw_input('Enter to end...\n')

评论(0) 阅读(1553)