---恢复内容开始---
从三角数开始，循环到八角数，再到三角数，求这6个数的和
这个比较复杂，代码在网上找的
Java：
package project61; import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set; public class P61
{
static enum Type {
TRIANGLE, SQUARE, PENTAGONAL, HEXAGONAL, HEPTAGONAL, OCTAGONAL;
} static class Suffix {
public Type type;
public int val; public Suffix(Type type, int val) {
this.type = type;
this.val = val;
}
} static class State {
public List<Integer> vals;
public Set<Type> used;
public int suffix; public State(int starting) {
this.vals = new ArrayList<Integer>();
this.used = new HashSet<Type>();
this.suffix = starting % 100;
this.vals.add(starting);
this.used.add(Type.OCTAGONAL);
} public State(State state, Suffix newval) {
this.vals = new ArrayList<Integer>(state.vals);
this.used = new HashSet<Type>(state.used);
this.used.add(newval.type);
this.vals.add(state.suffix * 100 + newval.val);
this.suffix = newval.val;
}
} public Map<Integer, Set<Suffix>> prefixmap = new HashMap<Integer, Set<Suffix>>(); public P61() throws Exception
{
Queue<State> search = new LinkedList<State>(); int n = 1;
boolean bounds = true;
while (bounds) {
int tri = n * (n + 1) / 2;
int sq = n * n;
int pent = n * (3 * n - 1) / 2;
int hex = n * (2 * n - 1);
int hept = n * (5 * n - 3) / 2;
int oct = n * (3 * n - 2); if (tri < 10000 && tri >= 1000)
addPrefix(tri / 100, new Suffix(Type.TRIANGLE, tri % 100));
if (sq < 10000 && sq >= 1000)
addPrefix(sq / 100, new Suffix(Type.SQUARE, sq % 100));
if (pent < 10000 && pent >= 1000)
addPrefix(pent / 100, new Suffix(Type.PENTAGONAL, pent % 100));
if (hex < 10000 && hex >= 1000)
addPrefix(hex / 100, new Suffix(Type.HEXAGONAL, hex % 100));
if (hept < 10000 && hept >= 1000)
addPrefix(hept / 100, new Suffix(Type.HEPTAGONAL, hept % 100));
if (oct < 10000 && oct >= 1000)
search.add(new State(oct)); bounds &= (tri < 10000);
n++;
} while (search.size() > 0) {
State cur = search.poll();
// System.out.println(cur);
if (cur.vals.size() == 6 && cur.used.size() == 6 &&
(cur.vals.get(0) / 100 == cur.vals.get(5) % 100)) {
int sum = 0;
for (int val : cur.vals) {
System.out.println(val);
sum += val;
}
System.out.println();
System.out.println(sum);
} else {
Set<Suffix> candidates = prefixmap.get(cur.suffix);
if (candidates != null) {
for (Suffix suff : candidates) {
if (!cur.used.contains(suff.type)) {
State newstate = new State(cur, suff);
search.add(newstate);
}
}
}
}
}
} public void addPrefix(int prefix, Suffix value) {
if (!prefixmap.containsKey(prefix)) {
prefixmap.put(prefix, new HashSet<Suffix>());
}
prefixmap.get(prefix).add(value);
} public static void main(String[] args) throws Exception
{
new P61();
} }
Python：
代码1：
def main(p):
Tri = lambda n: (n * (n + 1)) / 2
Squ = lambda n: (n * n)
Pen = lambda n: (n * (3 * n - 1)) / 2
Hex = lambda n: (n * (2 * n - 1))
Hep = lambda n: (n * (5 * n - 3)) / 2
Oct = lambda n: (n * (3 * n - 2))
a = [[Tri, Squ, Pen, Hex, Hep, Oct][i] for i in p]
S = []
for fun in a:
S.append([[str(fun(i))]
for i in range(1000) if len(str(fun(i))) == 4])
ans = [S[0][:]]
for t in S[1:]:
ans.append([])
for j in ans[-2]:
for i in t:
if j[-1][2:] == i[0][:2]:
ans[-1].append(j + i)
for i in ans[5]:
if i[0][:2] == i[-1][2:]:
print sum(map(int,i))
def dfs(p, l):
r = len(p)
if l == r:
main(p)
else:
for i in range(l, r):
p[l] ,p[i] = p[i], p[l]
dfs(p, l + 1)
p[l] ,p[i] = p[i], p[l]
p = [0,1,2,3,4,5]
dfs(p, 1)根据dfs写的。。。。。
代码2：
from itertools import permutations def trig(n):
return n*(n+1)//2 def quad(n):
return n*n def penta(n):
return n*(3*n-1)//2 def hexa(n):
return n*(2*n-1) def hepta(n):
return n*(5*n-3)//2 def octo(n):
return n*(3*n-2) def ajout(d,k,x):
try:
d[k].append(x)
except:
d[k]=[x] listef=[trig,quad,penta,hexa,hepta,octo] listedict=[dict() for i in range(6)] listenb=[[f(n) for n in range(150) if f(n)>=1000 and f(n)<=9999 and str(f(n))[-2]!=''] for f in listef] print listenb for i in range(6):
for x in listenb[i]:
ajout(listedict[i],x//100,x) print listedict liste_possibilites=[] for p in permutations([0,1,2,3,4]):
for x in listenb[-1]:
chaines=[[x]]
for i in range(5):
chaines2=[]
for c in chaines:
try:
nb=c[-1]
listecontinuation=listedict[p[i]][nb%100]
for y in listecontinuation:
chaines2.append(c+[y])
except:
continue
chaines=chaines2
liste_possibilites+=chaines print liste_possibilites solutions=[x for x in liste_possibilites if x[-1]%100==x[0]//100] solution=solutions[0] print(sum(solution))
1.求出所以的三角数到八角数
2.前两位相同的放在一起
3.循环的放在一起。