异度部落格

学习是一种生活态度。

0%

【题目描述】1000瓶药水,其中至多有1瓶剧毒,现在给你10只小狗在24小时内通过小狗试药的方式找出哪瓶药有毒或者全部无毒(小狗服完药20小时后才能判断是否中毒)

【题目来源】08腾讯

【题目分析】 方法一: 将药水进行二进制编号,比如第一瓶是0000000001,第十瓶是0000001010...... 将小狗1~10的编号,一号小狗对应二进制数的第一位,二号小狗对应第二位,以此类推. 比如:第一瓶药的第十位是1,则让第十只小狗喝下;第十瓶药的第八位和第十位是1,则让编号8,10的小狗喝下,依此类推 例如:第1,2,3条狗狗死了,那么组合成的二进制数为1110000000,转换成十进制就是896瓶药有毒

方法二: 将药分成10份,每份100瓶,在第零个小时将每一份药给一个小狗喝(也就是每条狗试100瓶) 过一个小时后,将第一份药平均分十份(也就是每份十瓶),每份让小狗喝下,第二份、第三份...亦如此类推 在过一个小时后,将第一份药的第一份药分十份(也就是每份一瓶),每份让小狗喝下,第二份、第三份...亦如此类推............ 过二十个小时后,比如第二条狗死了,那有毒的药就在第二个100瓶里面 过二十一个小时后,比如第四条狗死了,那有毒的药就在第二个100瓶里的第四个10瓶里 过二十二个小时后,比如第八条狗死了,那有毒的药就在第二个100瓶里的第四个10瓶里的第8瓶

转自:http://topic.csdn.net/u/20100919/10/b6561d69-bf8b-4e1a-a2a9-743f4edd52ff.html

【题目描述】1到N自然数排序。要求时间复杂度为O(n),空间复杂度为O(1)

【题目来源】华为

【题目分析】

【代码】

/**
1到N自然数排序(华为面试题)
要求:时间复杂度为O(n),空间复杂度为O(1)
*/
#include <iostream>
using namespace std;
int array[10] = {0, 2, 4, 6, 9, 8, 1, 3, 7, 5};
int n = 10;
void sort()
{
int t;
for(int i = 0; i < n; i++)
{
while(array[i] != i)
{
t = array[array[i]];
array[array[i]] = array[i];
array[i] = t;
}
}
}
void output()
{
for(int i = 0; i < 10; i++)
cout << array[i];
cout << endl;
}
int main()
{
sort();
output();
return 0;
}

什么是 MEF?

Managed Extensibility Framework(MEF)可以很容易的构造可扩展性的应用程序。MEF 提供了发现和组合能力,因此你可以选择来加载插件。

MEF 解决了什么问题?

  • MEF 赠送了一种简单的在运行时扩展问题。直到现在,任何程序你想支持插件模式,需要构建自己的架构。这些插件经常是特定应用的并且不能被多种实现重用的。
  • MEF 提供一个标准方式来让程序暴露自己,消耗外部扩展。扩展,天生的,能被不同的程序重用。然而,一个扩展需要实现特定应用。扩展可以依赖另一个扩展,MEF 确保它们以正确的顺序同时被装配。
  • MEF 允许在查询和筛选中使用额外的元数据来标记扩展。

MEF 如何工作?

  • 粗略的说,MEF 的核心由一个 catalog(目录)和一个 CompositionContainer 组成。一个 catalog 负责查找扩展,container 负责协调创建和符合的依赖。
  • MEF 第一个类是 ComposablePart。一个 Composable part 提供了一个或多个 Exports,也可以依赖于一个或多个由 Imports 提供的扩展。一个 composable part 也管理可以是 object 或给定类型的实例。MEF,然而,是一个可扩展的,额外的 ComposablePart 实现,它依附于 Import/Export 契约。
  • Exports 和 Imports 每个都有一个契约(Contract)。契约(Contract)是 exports 和 Imports 之间的桥梁。一个 export 契约由用来过滤的元数据组成。例如,它可以指定一个 export 提供的指定能力。
  • MEF 的容器和 Catalogs 交互来访问 composable parts。容器自己解决一部分依赖并暴露 Exports 给外界。如果你愿意,你可以自由去增加 composable part 的实例。
  • 一个 ComposablePart 返回一个 catalog,它在你的程序中很像一个扩展。它有宿主程序提供的 Imports,然后 Export 其他。
  • 默认 MEF composable part 实现使用 attribute 元数据来声明 exports 和 imports。这允许 MEF 来决定哪个 parts, imports 和 exports 是完全可用的。

C & 传统 C++

#include //设定插入点
#include //字符处理
#include //定义错误码
#include //浮点数处理
#include //文件输入/输出
#include //参数化输入/输出
#include //数据流输入/输出
#include //定义各种数据类型最值常量
#include //定义本地化函数
#include
//定义数学函数
#include //定义输入/输出函数
#include //定义杂项函数及内存分配函数
#include //字符串处理
#include //基于数组的输入/输出
#include //定义关于时间的函数
#include //宽字符处理及输入/输出
#include //宽字符分类

标准 C++ (同上的不再注释)

#include //STL 通用算法
#include //STL 位集容器
#include
#include
#include
#include
#include //复数类
#include
#include
#include
#include
#include //STL 双端队列容器
#include //异常处理类
#include
#include //STL 定义运算函数(代替运算符)
#include #include //STL 线性列表容器
#include
//STL 映射容器
#include
#include //基本输入/输出支持
#include //输入/输出系统使用的前置声明
#include
#include //基本输入流
#include //基本输出流
#include //STL 队列容器
#include //STL 集合容器
#include //基于字符串的流
#include //STL 堆栈容器
#include //标准异常类
#include //底层输入/输出支持
#include //字符串类
#include //STL 通用模板类
#include //STL 动态数组容器
#include
#include
using namespace std;

C99 增加

#include //复数处理
#include //浮点环境
#include //整数格式转换
#include //布尔环境
#include //整型环境
#include //通用类型数学宏

Qt 开发库是一个使用广泛的跨平台 GUI 开发库,可用于 Windows、Linux、Mac OSX 和许多手持平台。QT 具有良好结构化(但灵活)的面向对象的结构、清晰的文档以及直观的 API。自 Trolltech 公司被 Nokia 收购后,Qt 成为 Nokia 旗下的一个部门。

Python 的默认 GUI 是 Tkinter,PyQt 是跨平台应用程式框架 Qt 的 Python 绑定版本,同时也是 PyKDE(KDE API 的 Python 绑定)的基础。PyQt 支持 Linux 操作系统和其他 Unix ,以及 Mac OS X 操作系统和微软 Windows 。

#!/usr/bin/env python
#PyQt Hello World
import sys
from PyQt4 import QtCore,QtGui
app = QtGui.QApplication(sys.argv)
label = QtGui.QLabel("Hello World", None)
label.show()
sys.exit(app.exec_())

生产者-消费者问题是系统进程里面的一个经典问题,这里用 Python 简单模拟一下。

#!/usr/bin/env python
#生产者-消费者问题
import threading
from random import randint
from time import sleep, ctime
from Queue import Queue
#创建MyThread子类
class MyThread(threading.Thread):
def __init__(self, func, args, name = ''):
threading.Thread.__init__(self)
self.name = name
self.func = func
self.args = args
def getResult(self):
return self.res
def run(self):
print'starting', self.name, 'at:', ctime()
self.res = apply(self.func, self.args)
print self.name, 'finished at:', ctime()
#生产者与消费者问题
def writeQueue(queue):
queue.put('Anything', 1)
print "Producing object for Queue. Size now", queue.qsize()
def readQueue(queue):
val = queue.get(1)
print 'Consumed object from Queue. Size now', queue.qsize()
def produce(queue, loops):
for i in range(loops):
writeQueue(queue)
sleep(randint(1,3))
def consume(queue, loops):
for i in range(loops):
readQueue(queue)
sleep(randint(2,5))
def main():
funcs = [produce, consume]
nfuncs = range(len(funcs))
nloops = randint(2, 5)
queue = Queue(32)
threads = []
for i in nfuncs:
t = MyThread(funcs[i], (queue, nloops),funcs[i].__name__)
threads.append(t)
for i in nfuncs:
threads[i].start()
for i in nfuncs:
threads[i].join()
print 'All Done!!'
if __name__ == '__main__':
main()

Python 的文件遍历主要使用的 os 这个模块,这里为了方便显示同时使用了一个图形化的库 Tkinter。Tkinter 是 Python 自带的一个 GUI 开发库,虽然没有 PyQt 或 wxPython 那么强大,但是基本的使用绝对足够了。

#!/usr/bin/env python
#文件遍历GUI
import os
from time import sleep
from Tkinter import *
class DirList(object):
def __init__(self, initDir = None):
self.top = Tk()
self.label = Label(self.top, text = 'Directory Lister')
self.label.pack()

self.cwd = StringVar(self.top)
self.dirLabel = Label(self.top, fg = 'blue',
font = ('Helvetica', 12, 'bold'))
self.dirLabel.pack()
self.dirFrame = Frame(self.top)
self.dirScrollbar = Scrollbar(self.dirFrame)
self.dirScrollbar.pack(side = RIGHT, fill = Y)
self.dirListbox = Listbox(self.dirFrame, height = 15,width = 50,
yscrollcommand = self.dirScrollbar.set)
self.dirListbox.bind('<Double-l>', self.setDirAndShow)
self.dirScrollbar.config(command = self.dirListbox.yview)
self.dirListbox.pack(side = LEFT, fill = BOTH)
self.dirFrame.pack()
self.dirEntry = Entry(self.top, width = 50,
textvariable = self.cwd)
self.dirEntry.bind('<Return>', self.showList)
self.dirEntry.pack()
self.buttonFrame = Frame(self.top)
self.clearButton = Button(self.buttonFrame, text = 'Clear',
command = self.clearDir,
activeforeground = 'white',
activebackground = 'blue')
self.listButton = Button(self.buttonFrame, text = 'List Directory',
command = self.showList,
activeforeground = 'white',
activebackground = 'green')
self.quitButton = Button(self.buttonFrame, text = 'Quit',
command = self.top.quit,
activeforeground = 'white',
activebackground = 'red')
self.clearButton.pack(side = LEFT)
self.listButton.pack(side = LEFT)
self.quitButton.pack(side = LEFT)
self.buttonFrame.pack()
if initDir:
self.cwd.set(os.curdir)
self.showList()

#清空列表
def clearDir(self, event = None):
self.cwd.set('')
#设置目录并显示
def setDirAndShow(self, event = None):
self.lastDir = self.cwd.get()
self.dirListbox.cofig(selectbackground = 'red')
check = self.dirListbox.get(self.dirListbox.curselection())
if not check:
check = os.curdir
self.cwd.set(check)
self.showList()
#显示列表
def showList(self, event = None):
error = ''
tmp = self.cwd.get()
if not tmp:
tmp = os.curdir
if not os .path.exists(tmp):
error = tmp + ': no such file'
elif not os.path.isdir(tmp):
error = tmp + ':not a directory'
if error:
self.cwd.set(error)
self.top.update()
sleep(2)
if not (hasattr(self, 'last') and self.lastDir):
self.lastDir = os.curdir
self.cwd.set(self.lastDir)
self.dirListbox.config(selectbackground = 'LightSkyBlue')
self.top.update()
return
self.cwd.set('Fetching Directory contents...')
self.top.update()
dirlist = os.listdir(tmp)
os.chdir(tmp)
self.dirLabel.config(text = os.getcwd())
self.dirListbox.delete(0, END)
self.dirListbox.insert(END, os.curdir)
self.dirListbox.insert(END, os.pardir)
for eachFile in dirlist:
self.dirListbox.insert(END, eachFile)
self.cwd.set(os.curdir)
self.dirListbox.config(selectbackground = 'LightSkyBlue')
#主函数
def main():
dirList = DirList(os.curdir)
dirList.top.mainloop()
dirList.top.destroy()
if __name__ == '__main__':
main()

这里的程序并不复杂,下面主要对随机数据的生成部分进行分析

def randNumGen(self) :
numStr = '0123456789'
randNum = ''
for i in range(4) :
n = choice(numStr)
randNum += n
numStr = numStr.replace(n, '')
self.sysNum = randNum

这里由于数字是不重复的,所以可以先定义好一个 0-9 的数字串,然后用 choice 函数随机选出一个,之后删除这个数字,再次 choice,直到选出 4 位数字为止。

下面是完整的代码:

#!/usr/bin/env python
#猜数字游戏
from string import digits
from random import randint, choice
class GuessNumber(object) :
#构造器
def __init__(self) :
self.count = 0 #用于统计猜测次数
self.usrNums = [] #用户所猜数字
self.sysNum = '' #系统生成数字
self.results = [] #猜测结果
self.isWinner = False
#打印规则
def printRules(self) :
print """由系统随机生成不重复的四位数字,用户猜,之后系统进行提示。
A代表数字正确位置正确,B代表数字正确位置错误。
如正确答案为 5234,而猜的人猜 5346,则是 1A2B,其中有一个5的位置对了
,记为1A;3和4这两个数字对了,而位置没对,因此记为 2B,合起来就是 1A2B。
   接着猜的人再根据出题者的几A几B继续猜,直到猜中(即 4A0B)为止"""
#随机数字生成
def randNumGen(self) :
numStr = '0123456789'
randNum = ''
for i in range(4) :
n = choice(numStr)
randNum += n
numStr = numStr.replace(n, '')
self.sysNum = randNum
#print 'Debug >> SysNum::', self.sysNum
#数字输入
def numInput(self) :
self.count += 1
while True:
num = raw_input('输入您想要猜的数字:')
print 'Debug >> num::',num
if len(num) < 4 :
print '***错误: 位数小于四位,请重新输入'
continue
elif len(num) > 4:
print '***错误: 位数大于四位,请重新输入'
continue
if not self.isAllNumber(num) :
print '***错误: 您输入了非数字字符,请重新输入'
continue
elif self.hasSameDigit(num) :
print '***错误: 您输入了含有相同数字的数字串,请重新输入'
continue
else :
self.usrNums.append(num)
return num
#判断是否都是数字
def isAllNumber(self, num) :
for ch in num :
if ch not in digits :
return False
return True

#判断是否有相同的字符
def hasSameDigit(self, num) :
for i in range(len(num)) :
pos = num[i + 1 :].find(num[i])
if pos >= 0 :
return True
return False
#判断
def numJudge(self, sysNum, usrNum) :
countA = 0
countB = 0
for i in range(4) :
if usrNum[i] in sysNum :
if i == sysNum.find(usrNum[i]) :
countA += 1
else :
countB += 1
result = '%dA%dB' % (countA, countB)
self.results.append(result)
if countA == 4 :
self.isWinner = True
#显示迄今为止所有猜测结果
def showResults(self, usrNums, results) :
print '-' * 20
for i in range(self.count) :
print '(%d)/t%s/t%s' % (i + 1, usrNums[i], results[i])
print '-' * 20
if self.isWinner :
print 'Total: %d times' % self.count
print 'Congratulations! Your are winner !!'
#运行
def run(self) :
self.printRules()
self.randNumGen()
while not self.isWinner:
num = self.numInput()
self.numJudge(self.sysNum, num)
self.showResults(self.usrNums, self.results)
#主函数
def main() :
guessNumber = GuessNumber()
guessNumber.run()
if __name__ == '__main__' :
main()

Python 里面的 FTP 连接,主要依赖 ftplib 这个模块,具体请看帮助文档。

#!/usr/bin/env python
#FTP下载程序
import ftplib
import os
import socket
HOST = 'ftp.mozilla.org'
DIR = 'pub/mozilla.org/webtools'
FILE = 'bugzilla-LATEST.tar.gz'
def ftpDownload() :
try:
f = ftplib.FTP(HOST)
except (socket.error, socket.gaierror), e:
print 'ERROR: cannot connect "%s"' % HOST
return
print '>>Connect to host "%s"' % HOST
try:
f.login()
except ftplib.error_perm:
print 'ERROR: cannot login anonymously'
f.quit()
return
print '>>Logged in as "anonymous"'
try:
f.cwd(DIR)
except ftplib.error_perm:
print 'ERROR: cannot go to "%s"' % DIR
f.quit()
return
print '>>Go to "%s"' % DIR
try:
f.retrbinary('RETR %s' % FILE,
open(FILE, 'wb').write)
except ftplib.error_perm:
print 'ERROR: cannot read file "%s"' % FILE
os.unlink(FILE)
else:
print '>>Download "%s"' % FILE
f.quit()
return
def main() :
ftpDownload()
if __name__ == '__main__':
main()

所谓的网络爬虫就是利用程序抓取想要的网页或者数据。

下面对程序中所使用模块进行简单分析:

网络方面涉及 Python 的三个模块 htmllib,urllib,urlparse。
1)htmllib这个模块定义了一个可以担当在超文本标记语言(HTML)中解析文本格式文件的基类。该类不直接与 I/O 有关--它必须被提供字符串格式的输入,并且调用一个"格式设置"对象的方法来产生输出。该 HTMLParser 类被设计用来作为其他类增加功能性的基类,并且允许它的多数方法被扩展或者重载。该 HTMLParser 实现支持 HTML 2.0(描述在 RFC1866 中)语言。
2)urllib模块提供的上层接口,使我们可以像读取本地文件一样读取 www 和 ftp 上的数据。通过简单的函数调用,URL 所定位的资源就可以被你作为输入使用到你的程序中。如果再配以 re(正则表达式)模块,那么你就能够下载 Web 页面、提取信息、自动创建你所寻找的东西。urlretrieve 方法直接将远程数据下载到本地。参数 filename 指定了保存到本地的路径(如果未指定该参数,urllib 会生成一个临时文件来保存数据);
3)urlparse模块使我们能够轻松地把 URL 分解成元件(urlparse),之后,还能将这些元件重新组装成一个 URL(urljoin)。当我们处理 HTML 文档的时候,这项功能是非常方便的。

系统方面涉及 Python 的模块比较简单,主要是常用的sysos两个模块。主要用于文件夹的创建,文件路径的定位和判断等常用功能。这里不再介绍深入介绍。

输入输出方面使用了cStringIO模块。StringIO 的行为与 file 对象非常像,但它不是针对磁盘上文件,而是一个内存中的"文件",我们可以将操作磁盘文件那样来操作 StringIO。

formatter模块主要用于格式化输出。这里的格式化输出不仅仅是"格式化"输出而已。它可以将 HTML 解析器的标签和数据流转换为适合输出设备的事件流( event stream ),从 而 写将事件流相应的输出到设备上。

这个程序所使用的 Python 解释器版本为 2.6.5

下面是代码部分 NetCrawl.py

#!/usr/bin/env python
#网络爬虫程序
from sys import argv
from os import makedirs, unlink, sep
from os.path import dirname, exists, isdir, splitext
from string import replace, find, lower
from htmllib import HTMLParser
from urllib import urlretrieve
from urlparse import urlparse, urljoin
from formatter import DumbWriter, AbstractFormatter
from cStringIO import StringIO
class Downloader(object) :
#构造器
def __init__(self, url) :
self.url = url
self.file = self.filename(url)
#分析获取文件名
def filename(self, url, defFile = 'index.htm') :
parsedUrl = urlparse(url, 'http:', 0)
path = parsedUrl[1] + parsedUrl[2]
ext = splitext(path)
if ext[1] == '': #使用默认文件名
if path[-1] == '/':
path += defFile
else:
path += '/' + defFile
localDir = dirname(path)
if sep != '/':
localDir = replace(localDir, '/', sep)
if not isdir(localDir):
if exists(localDir): #文件存在删除
unlink(localDir)
makedirs(localDir)
return path
#下载页面
def download(self) :
try :
retval = urlretrieve(self.url, self.file)
except IOError:
retval = ('***ERROR: invalid URL "%s"' % self.url)
return retval
#分析保存链接
def parseAndGetLinks(self) :
self.parser = HTMLParser(AbstractFormatter( /
DumbWriter(StringIO())))
self.parser.feed(open(self.file).read())
self.parser.close()
return self.parser.anchorlist
class NetCrawler(object):
count = 0 #计数器
#构造器
def __init__(self, url) :
self.queue = [url]
self.seen = []
self.dom = urlparse(url)[1]
#获取页面
def getPage(self, url) :
dl = Downloader(url)
retval = dl.download()
if retval[0] == '*' :
print retval, '...skipping parse'
return
NetCrawler.count += 1
print '/n(', NetCrawler.count, ')'
print 'Url: ', url
print 'File: ', retval[0]
self.seen.append(url)
links = dl.parseAndGetLinks()
for eachLink in links :
if eachLink[ : 4] != 'http' and /
find(eachLink, '://') == -1:
eachLink = urljoin(url, eachLink)
print '*',eachLink
if find(lower(eachLink), 'mailto:') != -1:
print '... discarded, mailto link'
continue
if eachLink not in self.seen:
if find(eachLink, self.dom) == -1 :
print '... discarded, not in domain'
else :
if eachLink not in self.queue :
self.queue.append(eachLink)
print '... new, added to queue'
else :
print '... dirscarded, already in queue'
else :
print '... discarded, already processed'
#处理队列中的链接
def run(self) :
while self.queue :
url = self.queue.pop()
self.getPage(url)
#主函数
def main() :
#url = 'http://www.hao123.com/haoserver/index.htm'
if len(argv) > 1 :
url = argv[1]
else :
try :
url = raw_input('Enter starting URL: ')
expect (KeyboardInterrupt, EOFError) :
url = ''
if not url :
return
netCrawler = NetCrawler(url)
netCrawler.run()

if __name__ == '__main__' :
main()

这里的程序只是简单的抓取网页,如果要抓取指定网页可以加上也正则表达式(模块)来进行处理