一.
猴子吃桃問題：猴子第一天摘下若干個桃子，當(dāng)即吃了一半，還不癮，又多吃了一個 第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了。求第一天共摘了多少。
代碼如下：
if __name__=='__main__':
x=1;
for i in range(1,10):
x=x+1;
x*=2;
print(x);
1534個桃子。。。。
二.百米
import requests;
import re;
def get_calculate(url,session):
r=session.get(url);
str=re.findall(r"<div name='my_expr'>"+'.*'+'</div>=?',r.text);
cal=str[0].lstrip("<div name='my_expr'>");
cal=cal.rstrip(" </div>=");
cal=cal.replace('x','*');
print(cal);
return cal;
def calcu(cal):
num_list=re.findall(r'\d{2,4}',cal);
for i in range(0,len(num_list)):
num_list[i]=int(num_list[i]);
result=(num_list[0]+num_list[1])*(num_list[2]-num_list[3])-((num_list[4]+num_list[5]-num_list[6]))*num_list[7];
print(result);
return result;
def post_result(result,session):
payload={'pass_key':result};
r = session.post("http://ctf5.shiyanbar.com/jia/index.php?action=check_pass", data=payload);
print(r.text);
if __name__=='__main__':
session=requests.session();
cal=get_calculate('http://ctf5.shiyanbar.com/jia/index.php',session);
result=calcu(cal);
post_result(result,session);
圖一
如圖，直接上代碼解決，有坑是必須同個session get和post不然出不來結(jié)果。。。。
三.迷宮大逃亡
解決帶啊嗎如下所示：
import base64
def openfile():
result="";
f=open('in.txt','r');#open file
total_num=int(f.readline().strip());#get the number of maze
while(total_num!=0):
line=None;
while not line:
line=f.readline().strip();
scale=int(line);#maze scale
start=[];
for x in f.readline().strip().split():#get the start location
start.append(int(x)-1);
end=[];
for x in f.readline().strip().split():#get the end location
end.append(int(x)-1);
maze=[];
for m in range(scale):
maze.append(f.readline().strip());
r=pyqueue(len(maze[0]),start,end,maze);
result+=str(r.run());
total_num=total_num-1;
print(result);
flag = ""
for i in range(0, len(result), 8):
c = result[i:i + 8]
flag += chr(int(c, 2))
print(base64.b64decode(flag))
class pyqueue:
def __init__(self,_len,_start,_end,_maze):
self.len=_len #maze scale
self.start=_start;
self.end=_end;
self.maze=_maze;
self.queue=[self.start];#ininial location
self.steptrace=[];# trace route
self.success=0;# success flag
def Inquque(self,location):
self.queue.append(location);
self.steptrace.append(location);
return True;
def Qqueue(self):
temp=self.queue[0];
del(self.queue[0]);
return temp;
def Void(self,location):
try:
if location in self.steptrace or self.maze[location[0]][location[1]]=='X':
return;
else:
if location == self.end:
self.success = 1;
return;
self.steptrace.append(location);
self.Inquque(location);
return;
except:
print('error');
print(location);
def empty(self):
try:
self.queue[0];
return True;
except IndexError:
return False;
def addx(self,x):
x+=1;
if x>=self.len:
return x-1;
else:
return x;
def subx(self,x):
x-=1;
if x<0:
return x+1;
else:
return x;
def run(self):
return str(self.wayto_mazeend());
def wayto_mazeend(self):
while self.empty():
location=self.Qqueue();
self.Void([self.addx(location[0]),location[1]]);
self.Void([self.subx(location[0]),location[1]]);
self.Void([location[0],self.addx(location[1])]);
self.Void([location[0],self.subx(location[1])]);
if self.success==1:
return 1;
return 0;
if __name__=='__main__':
openfile();
這是用了bfs廣度優(yōu)先算法解決出來的，程序邏輯思路是每一個迷宮能成功走出就返回1，不能就返回0，然后就直接把幾百個迷宮走一次，接著直接每八位為一段，返回所謂的ASCII編碼字符，最后是一個base64編碼解出來URL直接獲取flag。
這道題目坑的地方在于要除掉URL后面的字母，接著訪問新題目的鏈接才是flag...
四.三羊生瑞
這道題目就是明顯的計算式子，想法不難有點繁瑣。。。
'''
祥a 瑞b 生c 輝d
+ 三e 羊f 獻(xiàn)g 瑞b
-——————
三e 羊f 生c 瑞b 氣h
'''
a=9;
e=1;
f=0;
def find():
for b in range(0,10):
for c in range(0,10):
for d in range(0,10):
for g in range(0,10):
for h in range(0,10):
if((e*10000+f*1000+c*100+b*10+h)==((a*1000+b*100+c*10+d)+(e*1000+f*100+g*10+b))):
if a!=b and a!=c and a!=d and a!=e and a!=f and a!=g and a!=h:
if b!=c and b!=d and b!=e and b!=f and b!=g and b!=h:
if c!=d and c!=e and c!=f and c!=g and c!=h:
if d!=e and d!=f and d!=g and d!=h:
if e!=f and e!=g and e!=h:
if f!=g and f!=h:
if g!=h:
print(a, b, c, d);
print(e, f, g, b);
print(e, f, c, b, h);
return;
if __name__=='__main__':
find();
想起以前做過某道找數(shù)字的題目，做完以后還和社長去華師吃飯呢。。。。懷念。。
五.找素數(shù)
設(shè)一個等差數(shù)列，首元素為367，公差為186, 現(xiàn)在要求找出屬于該等差數(shù)列中的第151個素數(shù)并輸出。
這道題難點在于素數(shù)快速判斷，這里學(xué)習(xí)一波。。。
import math;
def is_prime(num):
if num==2 or num==3:
return 1;
elif num%6!=1 and num%6!=5:
return 0;
else:
temp=math.sqrt(num);
i=5;
while i<=temp:
if num%i==0 or num%(i+2)==0:
return 0;
else:
i+=6;
return 1;
if __name__=='__main__':
a=[];
i=0;
while(len(a)<151):
temp=367+186*i;
if is_prime(temp)==1:
a.append(temp);
i+=1;
print(a[len(a)-1]);
p1
這里的方法還是學(xué)下。。。
六.小球下落
這道題目算是二叉樹簡單概念的應(yīng)用了，最后要找葉子編號。。。
if __name__=='__main__':
a = [0 for i in range(0, 65536)];
for i in range(12345):
temp=1;
for x in range(0,15):
if(a[temp]==0):
a[temp]=~a[temp];
temp=temp*2;
else:
a[temp]=~a[temp];
temp=temp*2+1;
if i==12344:
print(temp);
難度基本可以接受。。
七.普里姆路徑
這道題目是BFS算法思想的應(yīng)用，主要是中間這一步生成新數(shù)字的做法有點沒接觸過，學(xué)習(xí)一波了。。。
import math
def is_prime(num):
if num==2 or num==3:
return 1;
elif num%6!=1 and num%6!=5:
return 0;
else:
temp=math.sqrt(num);
i=5;
while i<=temp:
if num%i==0 or num%(i+2)==0:
return 0;
else:
i+=6;
return 1;
class node:
def __init__(self,element,step):
self.element=element;
self.step=step;
def bfs():
start=1373;
end=8017;
Queue=[node(start,0)];
visited=[start];
while(len(Queue)!=0):
now=Queue[0];
del Queue[0];
if now.element==end:
return now.step;
else:
for i in range(4):
for j in range(10):
if i==0 and j==0:
continue;
else:
temp=int(str(now.element)[:i]+str(j)+str(now.element)[i+1:]);
if is_prime(temp)==1:
if temp not in visited:
visited.append(temp);
Queue.append(node(temp,now.step+1));
return False;
if __name__ == '__main__':
print(bfs());
總體還行，學(xué)習(xí)一波。。
八.大數(shù)模運算
這道題目主要是考察幾條數(shù)學(xué)運算式子，如下：
if __name__ == '__main__':
key1 = key2 = key3 = 0;
for i in range(0, 12346):
key1 += 3 ** i % 9901;
key2 += 5 ** i % 9901;
key3 += 823 ** i % 9901;
print((key1 * key2 * key3) % 9901);
p2
九.括號表達(dá)式
一個括號表達(dá)式可以按照如下的規(guī)則表示，就是每個右括號之前的左括號數(shù)。
比如(((()()())))，每個右括號之前的左括號數(shù)序列為P=4 5 6 6 6 6，而每個右括號所在的括號內(nèi)包含的括號數(shù)為W=1 1 1 4 5 6。
現(xiàn)在給定一個括號表達(dá)式為 4 6 6 6 6 8 9 9 9，輸出每個右括號所在的括號內(nèi)包含的括號數(shù)。
這道題目主要是要研究規(guī)律，從而找到位置差以及括號差之間的關(guān)系。代碼如下所示：
if __name__ == '__main__':
left=[0,4,6,6,6,6,8,9,9,9];
lists=[];
for i in range(1,len(left)):
j=i-1;
while(left[i]-left[j]<i-j):
j-=1;
print(i-j);
lists.append(i-j);
for i in lists:
print(i);
今天這幾道總體難度還行。。。
十.大數(shù)據(jù)問題
這道題直接暴力求解的。。
if __name__ == '__main__':
sum=0;
for i in range(1,6790):
sum+=math.factorial(i);
print(sum%100000)
十一.斐波那契數(shù)列
這個比較熟悉了，不迭代了直接調(diào)用如下代碼
def function(num):
lists=[1,1,1];
sum=0;
i=0;
if num<=2:
print(3);
else:
while(i<num):
sum=lists[i]+lists[i+1]+lists[i+2];
lists.append(sum);
i+=1;
print(lists[num]);
if __name__ == '__main__':
function(99)
十二.聰明的打字員
這道題目怎么說呢，恕我太蠢，C++的算法寫法看不懂，只能上所謂的暴力解法了。。。
def fun(a,depth,b):
if(depth==1):
for i in a:
b[-depth]=i;
yield b;
else:
for i in a:
b[-depth]=i;
for j in fun(a,depth-1,b):
yield j;
def func():
time=0;
step=[0,1,2,3,4,5];
while(1):
time+=1;
for i in fun(step,time,[1]*time):
work=0;
a=[1,2,3,4,5,6];
for j in i:
if(j==0):
a[work],a[0]=a[0],a[work];
elif(j==1):
a[work],a[5]=a[5],a[work];
elif(j==2):
if(a[work]<9):
a[work]+=1;
elif(j==3):
if(a[work]>0):
a[work]-=1;
elif(j==4):
if(work>0):
work-=1;
elif(j==5):
if(work<5):
work+=1;
if(a==[6,5,4,3,2,1]):
print(time);
return;
print(time);
if __name__=='__main__':
func();
解法時間比較長，差不多要五分鐘。。。。
十三.二叉樹遍歷
這個順便學(xué)一波二叉樹遍歷的python寫法，代碼如下：
class TreeNode(object):
def __init__(self):
self.data='#';
self.l_child=None;
self.r_child=None;
class Tree(TreeNode):
def create_tree(self,tree):
data=input('->');
if data=='#':
tree=None;
else:
tree.data=data;
tree.l_child=TreeNode();
self.create_tree(tree.l_child);
tree.r_child=TreeNode();
self.create_tree(tree.r_child);
def visit(self,tree):
if tree.data is not '#':
print(tree.data);
print('\t');
def pre_order(self,tree):
if tree is not None:
self.visit(tree);
self.pre_order(tree.l_child);
self.pre_order(tree.r_child);
def in_order(self,tree):
if tree is not None:
self.in_order(tree.l_child);
self.visit(tree);
self.in_order(tree.r_child);
def post_order(self,tree):
if tree is not None:
self.post_order(tree.l_child);
self.post_order(tree.r_child);
self.visit(tree);
if __name__=='__main__':
t=TreeNode();
tree=Tree();
tree.create_tree(t);
tree.pre_order(t);
print('\n');
tree.in_order(t);
print('\n');
tree.post_order(t);
二叉樹里面這種遞歸的做法是真的多。。。
十四.約瑟夫問題
def kill(people,num):
work=0;
while(len(people)>=12):
if people.count(1)<12:
return False;
else:
work=(work+num-1)%len(people);
del a[work];
return True;
if __name__=='__main__':
for i in range(13,2000000):
a = [1] * 12 + [0] * 12;
if kill(a,i)==True:
print(i);
break;
else:
continue;
十五.雙基回文數(shù)
這道題目主要學(xué)習(xí)了進(jìn)制轉(zhuǎn)換法吧，記清楚就行。。
def handle(value,hex_number):
sss='';
while(value!=0):
sss+=str(int(value%hex_number));
value=((value-value%hex_number)/hex_number);
return sss[::-1];
def ok(number):
for i in range(0,int(len(number)/2)):
if number[i]!=number[len(number)-1-i]:
return False;
return True;
if __name__=='__main__':
sum=1600000
while(1):
times=0;
for i in range(2,11):
if(ok(handle(sum,i))):
times+=1;
if times>1:
print(sum);
break;
sum+=1;
十六.兩個最大字串和
這道題目看了賊久，最后還是用貪心算法解決的，直接定義貪心算法的條件如下：
p3
就是如果當(dāng)前子序列和為負(fù)數(shù)那就直接丟棄掉就行。。
最后上我的代碼如下：
a=[-132,133,134,-11,12,-139,-140,62,63,-64,65,66,67,
1,2,3,4,5,-6,7,-48,-49,50,138,16,17,20,
101,102,-103,104,-105,106,146,147,148,-107,108,109,110,96,
21,-22,23,-24,-25,25,-27,-28,-29,30,
41,-42,8,9,10,-46,-47,
51,52,-53,54,-55,-56,57,-58,59,60,
73,-74,75,-71,-72,18,-97,-98,19,-129,130,
-137,136,-13,14,144,-145,15,128,
77,-78,-31,32,35,-76,149,-150,99,100,119,
91,-92,-93,94,95,116,117,114,118,120,
81,82,83,-84,85,-122,-123,
112,111,-43,44,45,-113,-115,36,-37,-38,39,40,25,126,127,
131,-135,61,-69,70,
141,-142,143,-86,68,-87,-90,
121,-88,89,-124,-179,-80,-33,34]
if __name__=='__main__':
value1=[9999]*150;
value2=[9999]*150;
sum,max=0,0;
for i in range(0,len(a),1):
if(sum<0):
sum=a[i];
else:
sum+=a[i];
if sum>max:
max=sum;
value1[i]=max;
sum,max=0,0;
for i in range(149,-1,-1):
if (sum < 0):
sum = a[i];
else:
sum += a[i];
if sum > max:
max = sum;
value2[i] = max;
for i in range(0,149,1):
if(value1[i]+value2[i+1]>max):
max=value1[i]+value2[i+1];
print(max);
算法還是要多學(xué)學(xué)的。。。
十七.分?jǐn)?shù)拆分
1/400=1/x+1/2y
也即1/x=1/400-1/2y=1/2(1/200-1/y)=1/2((y-200)/200y)=(y-200)/400y
也即x=400y/(y-200)由于x,y皆為正整數(shù)，故y>200
當(dāng)x=y時
1=400/x-200 x-200=400 x=600
代入y=700算出x=560因此y應(yīng)該小于600
故200<y<600
count=0
num_list=[]
for y in range(201,600):
if (400*y)%(y-200)==0:
count=count+1
str_add=str((400*y)/(y-200))+':'+str(y)
num_list.append(str_add)
print(num_list)
print('CTF{'+str(count)+'}')
十八.ascii art
這道題有點傻逼，就是直接替換而已。。。
import requests;
import re;
if __name__=='__main__':
url='http://ctf5.shiyanbar.com/ppc/acsii.php';
s=requests.session()
response=s.get(url);
patten=r'red">'+'.*'+'</div>';
num=re.findall(patten,response.text)[0];
num = num.replace(' xxx <br />x x<br />x x<br />x x<br /> xxx <br />','0')
num = num.replace(' xx<br /> x x <br /> x <br /> x <br />xxxxx<br />','1')
num = num.replace(' xx<br> x x <br> x <br> x <br>xxxxx<br><br/>','1')
num = num.replace(' xxx <br />x x <br /> xx <br /> x <br />xxxxx<br />','2')
num = num.replace(' xxx <br />x x<br /> xx <br />x x<br /> xxx <br />','8')
num = num.replace('xxxxx<br />x <br /> xxxx<br /> x<br />xxxxx<br />', '5')
num = num.replace(' x x<br />x x<br /> xxxxx<br /> x<br /> x<br />','4')
num = num.replace('xxxxx<br />x <br /> xxxx<br /> x<br />xxxxx<br />', '5')
num = num.replace('<br/>', '');
num=num.replace('red">','');
num=num.replace('</div>','');
response1=s.post(url,data={'inputNumber':num});
print(response1.text);
十九.速度爆破
這題難度很低，代碼
import requests;
import re;
import hashlib;
def hash_key(arg):
hash = hashlib.md5();
hash.update(arg.encode());
hash_sha=hashlib.sha1();
hash_sha.update(hash.hexdigest().encode())
return hash_sha.hexdigest()
if __name__=='__main__':
url='http://ctf5.shiyanbar.com/ppc/sd.php';
s=requests.session()
response=s.get(url);
patten=r'red">'+'.*'+'</div>';
num=re.findall(patten,response.text)[0];
num = num.replace('red">', '');
num = num.replace('</div>', '');
for i in range(0,100000):
if hash_key(str(i))==num:
break;
response1=s.post(url,data={'inputNumber':i});
print(response1.text);
二十.海量約瑟夫問題
這個有個公式推導(dǎo)，可以解決一般的約瑟夫問題，如下圖：
p4
通用代碼如下所示：
def process(n,m):
if(n<1 or m<1):
return False;
else:
flag=0;
result1,result2=0,0;
for i in range(2,n+1,1):
if(flag==0):
result1 = (result2 + m) % i;
flag=1;
else:
result2 = (result1 + m) % i;
flag = 0;
print(i);
return lambda x:result1 if(flag==1) else result2;
if __name__=='__main__':
n = 57109519409189850198608692898492839208109598203852985209815058928520938958906207207017014242749827958752975981705872782758927827398578971498749287481591758917982491;
print(process(n,2)%129119417519);
但是這個并無法解決海量數(shù)據(jù)時的問題，看了writeup代碼也是出錯的，有一個答主的代碼很神奇卻對了，如下：
>>>n=57109519409189850198608692898492839208109598203852985209815058928520938958906207207017014242749827958752975981705872782758927827398578971498749287481591758917982491
>>>((n-2**543)*2+1)%129119417519
想不懂啥道理。。。。不過這一波接觸了海量數(shù)據(jù)以后發(fā)現(xiàn)，數(shù)據(jù)一多真的算法都不一樣了。。。。差好大
二十一.Noise
這道題目就主要是處理圖片躁點，沒學(xué)過這個認(rèn)真學(xué)一下。。
if __name__=='__main__':
a = ['0'] * 256 * 256
from PIL import Image
im = Image.open("noise.png")
img = Image.new('RGB', (256, 256), (255, 255, 255))
loding = img.load()
sum = 0
for x in range(0, 256):
for y in range(0, 256):
i = im.getpixel((x, y))[1]
j = im.getpixel((x, y))[2]
loding[i, j] = (0, 0, 0)
sum += 1
if sum > 30000:
break
img.show()
二十二.hashkill
刷多了算法題來做這種程序編寫題真是so easy。。。
import hashlib;
import os;
def hash_key(arg):
hash = hashlib.md5();
hash.update(arg.encode());
return hash.hexdigest()
if __name__=='__main__':
location=["thebronx","brooklyn","manhattan","queens","statenisland"];
for i in range(0,1001):
for y in location:
for j in range(10000, 15000):
str1 = 'ctf{' + str(i) + '_' +y+'_'+str(j)+'}'
if(hash_key(str1)=='6ac66ed89ef9654cf25eb88c21f4ecd0'):
print(str1);
os._exit(0);
二十三.求解
這道題就是簡單凱撒加密而已，就是string類型可以索引訪問這一點學(xué)到了。。。
if __name__=='__main__':
list = 'abcdefghijklmnopqrstuvwxyz'
newlist = ''
for i in range(len(list)):
newlist += list[(5 * i + 11) % 26]
y = 'xztiofwhf'
x = ''
for j in y:
x += list[newlist.find(j)] # 查找新列表字符對應(yīng)的位置，在舊列表同樣的位置即為flag
print(newlist.find('x'));
二十四.
