# 发现长模式

``1, 2, 3, 4, 7, 15, 27, 30, 31, 81` `

### 6 Solutions collect form web for “发现长模式”

` `#include <stdio.h> #include <stdlib.h> #include <math.h> #include <memory.h> #include <time.h> struct Factor { int a; int k; struct Factor *next; }; struct Factor *factors = 0; int factorsL=0; void ConstructFactors(int R) { int a,k,C; int R2; struct Factor *f; float seconds; clock_t end; clock_t start = clock(); if (factors) free(factors); factors = malloc (sizeof(struct Factor) *((R>>1) + 1)); R2 = R>>1 ; for (a=0;a<=R2;a++) { factors[a].a= a; factors[a].k=1; factors[a].next=NULL; } factorsL=R2+1; R2 = floor(sqrt(R)); for (k=2; k<=R2; k++) { a=1; C=a*k*(k+1); while (C<R) { C >>= 1; f=malloc(sizeof(struct Factor)); *f=factors[C]; factors[C].a=a; factors[C].k=k; factors[C].next=f; a++; C=a*k*(k+1); } } end = clock(); seconds = (float)(end - start) / CLOCKS_PER_SEC; printf("Construct Table: %f\n",seconds); } void DestructFactors() { int i; struct Factor *f; for (i=0;i<factorsL;i++) { while (factors[i].next) { f=factors[i].next->next; free(factors[i].next); factors[i].next=f; } } free(factors); factors=NULL; factorsL=0; } int ipow(int base, int exp) { int result = 1; while (exp) { if (exp & 1) result *= base; exp >>= 1; base *= base; } return result; } void findGeo(int **bestSolution, int *bestSolutionL,int *Arr, int L) { int i,j,D; int mustExistToBeBetter; int R=Arr[L-1]-Arr[0]; int *possibleSolution; int possibleSolutionL=0; int exp; int NextVal; int idx; int kMax,aMax; float seconds; clock_t end; clock_t start = clock(); kMax = floor(sqrt(R)); aMax = floor(R/2); ConstructFactors(R); *bestSolutionL=2; *bestSolution=malloc(0); possibleSolution = malloc(sizeof(int)*(R+1)); struct Factor *f; int *H=malloc(sizeof(int)*(R+1)); memset(H,0, sizeof(int)*(R+1)); for (i=0;i<L;i++) { H[ Arr[i]-Arr[0] ]=1; } for (i=0; i<L-2;i++) { for (j=i+2; j<L; j++) { D=Arr[j]-Arr[i]; if (D & 1) continue; f = factors + (D >>1); while (f) { idx=Arr[i] + f->a * f->k - Arr[0]; if ((f->k <= kMax)&& (f->a<aMax)&&(idx<=R)&&H[idx]) { if (f->k ==1) { mustExistToBeBetter = Arr[i] + f->a * (*bestSolutionL); } else { mustExistToBeBetter = Arr[i] + f->a * f->k * (ipow(f->k,*bestSolutionL) - 1)/(f->k-1); } if (mustExistToBeBetter< Arr[L-1]+1) { idx= floor(mustExistToBeBetter - Arr[0]); } else { idx = R+1; } if ((idx<=R)&&H[idx]) { possibleSolution[0]=Arr[i]; possibleSolution[1]=Arr[i] + f->a*f->k; possibleSolution[2]=Arr[j]; possibleSolutionL=3; exp = f->k * f->k * f->k; NextVal = Arr[j] + f->a * exp; idx=NextVal - Arr[0]; while ( (idx<=R) && H[idx]) { possibleSolution[possibleSolutionL]=NextVal; possibleSolutionL++; exp = exp * f->k; NextVal = NextVal + f->a * exp; idx=NextVal - Arr[0]; } if (possibleSolutionL > *bestSolutionL) { free(*bestSolution); *bestSolution = possibleSolution; possibleSolution = malloc(sizeof(int)*(R+1)); *bestSolutionL=possibleSolutionL; kMax= floor( pow (R, 1/ (*bestSolutionL) )); aMax= floor(R / (*bestSolutionL)); } } } f=f->next; } } } if (*bestSolutionL == 2) { free(*bestSolution); possibleSolutionL=0; for (i=0; (i<2)&&(i<L); i++ ) { possibleSolution[possibleSolutionL]=Arr[i]; possibleSolutionL++; } *bestSolution = possibleSolution; *bestSolutionL=possibleSolutionL; } else { free(possibleSolution); } DestructFactors(); free(H); end = clock(); seconds = (float)(end - start) / CLOCKS_PER_SEC; printf("findGeo: %f\n",seconds); } int compareInt (const void * a, const void * b) { return *(int *)a - *(int *)b; } int main(void) { int N=100000; int R=10000000; int *A = malloc(sizeof(int)*N); int *Sol; int SolL; int i; int *S=malloc(sizeof(int)*R); for (i=0;i<R;i++) S[i]=i+1; for (i=0;i<N;i++) { int r = rand() % (Ri); A[i]=S[r]; S[r]=S[Ri-1]; } free(S); qsort(A,N,sizeof(int),compareInt); /* int step = floor(R/N); A[0]=1; for (i=1;i<N;i++) { A[i]=A[i-1]+step; } */ findGeo(&Sol,&SolL,A,N); printf("["); for (i=0;i<SolL;i++) { if (i>0) printf(","); printf("%d",Sol[i]); } printf("]\n"); printf("Size: %d\n",SolL); free(Sol); free(A); return EXIT_SUCCESS; }` `

1.-构造一个长度为M的数组H，使得如果我存在于初始数组中，M [i – S [0]] =真，如果不存在，则为假。

2.对于数组S [j]中的每一对，S [i]做：

2.1检查它是否是可能的解决scheme的第一和第三要素。 为此，计算满足方程S（i）= S（j）+ AK + AK ^ 2的所有可能的A，K对。 检查这个问题 ，看看如何解决这个问题。 并检查是否存在第二个元素：S [i] + A * K

2.2检查还有我们拥有的最好的解决scheme还存在元素一个位置。 例如，如果到目前为止最好的解决scheme是4个元素，那么检查是否存在元素A [j] + A K + A K ^ 2 + A K ^ 3 + A K ^ 4

2.3如果2.1和2.2是正确的，那么迭代这个系列多久，并设置为最佳解决scheme，直到现在是最后一个。

` `function getAKs(A) { if (A / 2 != Math.floor(A / 2)) return []; var solution = []; var i; var SR3 = Math.pow(A, 1 / 3); for (i = 1; i <= SR3; i++) { var B, C; C = i; B = A / (C * (C + 1)); if (B == Math.floor(B)) { solution.push([B, C]); } B = i; C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2; if (C == Math.floor(C)) { solution.push([B, C]); } } return solution; } function getBestGeometricSequence(S) { var i, j, k; var bestSolution = []; var H = Array(S[S.length-1]-S[0]); for (i = 0; i < S.length; i++) H[S[i] - S[0]] = true; for (i = 0; i < S.length; i++) { for (j = 0; j < i; j++) { var PossibleAKs = getAKs(S[i] - S[j]); for (k = 0; k < PossibleAKs.length; k++) { var A = PossibleAKs[k][0]; var K = PossibleAKs[k][17]; var mustExistToBeBetter; if (K==1) { mustExistToBeBetter = S[j] + A * bestSolution.length; } else { mustExistToBeBetter = S[j] + A * K * (Math.pow(K,bestSolution.length) - 1)/(K-1); } if ((H[S[j] + A * K - S[0]]) && (H[mustExistToBeBetter - S[0]])) { var possibleSolution=[S[j],S[j] + A * K,S[i]]; exp = K * K * K; var NextVal = S[i] + A * exp; while (H[NextVal - S[0]] === true) { possibleSolution.push(NextVal); exp = exp * K; NextVal = NextVal + A * exp; } if (possibleSolution.length > bestSolution.length) { bestSolution = possibleSolution; } } } } } return bestSolution; } //var A= [ 1, 2, 3,5,7, 15, 27, 30,31, 81]; var A=[]; for (i=1;i<=3000;i++) { A.push(i); } var sol=getBestGeometricSequence(A); \$("#result").html(JSON.stringify(sol));` `

` `var input = [0.7, 1, 2, 3, 4, 7, 15, 27, 30, 31, 81], output = [], indexes, values, i, index, value, i_max_length, i1, i2, i3, j1, j2, j3, difference12a, difference23a, difference12b, difference23b, scale_factor, common_ratio_a, common_ratio_b, common_ratio_c, error, EPSILON = 1e-9, common_ratio_is_integer, resultDiv = \$("#result"); for (i1 = 0; i1 < input.length - 2; ++i1) { for (i2 = i1 + 1; i2 < input.length - 1; ++i2) { scale_factor = difference12a = input[i2] - input[i1]; for (i3 = i2 + 1; i3 < input.length; ++i3) { difference23a = input[i3] - input[i2]; common_ratio_1a = difference23a / difference12a; common_ratio_2a = Math.round(common_ratio_1a); error = Math.abs((common_ratio_2a - common_ratio_1a) / common_ratio_1a); common_ratio_is_integer = error < EPSILON; if (common_ratio_2a > 1 && common_ratio_is_integer) { indexes = [i1, i2, i3]; j1 = i2; j2 = i3 difference12b = difference23a; for (j3 = j2 + 1; j3 < input.length; ++j3) { difference23b = input[j3] - input[j2]; common_ratio_1b = difference23b / difference12b; common_ratio_2b = Math.round(common_ratio_1b); error = Math.abs((common_ratio_2b - common_ratio_1b) / common_ratio_1b); common_ratio_is_integer = error < EPSILON; if (common_ratio_is_integer && common_ratio_2a === common_ratio_2b) { indexes.push(j3); j1 = j2; j2 = j3 difference12b = difference23b; } } values = []; for (i = 0; i < indexes.length; ++i) { index = indexes[i]; value = input[index]; values.push(value); } output.push(values); } } } } if (output !== []) { i_max_length = 0; for (i = 1; i < output.length; ++i) { if (output[i_max_length].length < output[i].length) i_max_length = i; } for (i = 0; i < output.length; ++i) { if (output[i_max_length].length == output[i].length) resultDiv.append("<p>[" + output[i] + "]</p>"); } }` `

` `[1, 3, 7, 15, 31]` `

` `function bsearch(Arr,Val, left,right) { if (left == right) return left; var m=Math.floor((left + right) /2); if (Val <= Arr[m]) { return bsearch(Arr,Val,left,m); } else { return bsearch(Arr,Val,m+1,right); } } function findLongestGeometricSequence(S) { var bestSolution=[]; var i,j,k; var H={}; for (i=0;i<S.length;i++) H[S[i]]=true; for (i=0;i<S.length;i++) { for (j=0;j<i;j++) { for (k=j+1;k<i;) { var possibleSolution=[S[j],S[k],S[i]]; var K = (S[i] - S[k]) / (S[k] - S[j]); var A = (S[k] - S[j]) * (S[k] - S[j]) / (S[i] - S[k]); if ((Math.floor(K) == K) && (Math.floor(A)==A)) { exp= K*K*K; var NextVal= S[i] + A * exp; while (H[NextVal] === true) { possibleSolution.push(NextVal); exp = exp * K; NextVal= NextVal + A * exp; } if (possibleSolution.length > bestSolution.length) bestSolution=possibleSolution; K--; } else { K=Math.floor(K); } if (K>0) { var NextPossibleMidValue= (S[i] + K*S[j]) / (K +1); k++; if (S[k]<NextPossibleMidValue) { k=bsearch(S,NextPossibleMidValue, k+1, i); } } else { k=i; } } } } return bestSolution; } function Run() { var MyS= [0.7, 1, 2, 3, 4, 5,6,7, 15, 27, 30,31, 81]; var sol = findLongestGeometricSequence(MyS); alert(JSON.stringify(sol)); }` `

` `from math import sqrt def add_precalc(precalc, end, (a, k), count, res, N): if end + a * k ** res[1]["count"] > N: return x = end + a * k ** count if x > N or x < 0: return if precalc[x] is None: return if (a, k) not in precalc[x]: precalc[x][(a, k)] = count return def factors(n): res = [] for x in range(1, int(sqrt(n)) + 1): if n % x == 0: y = n / x res.append((x, y)) res.append((y, x)) return res def work(input): precalc = [None] * (max(input) + 1) for x in input: precalc[x] = {} N = max(input) res = ((0, 0), {"end":0, "count":0}) for i, x in enumerate(input): for y in input[i::-1]: for a, k in factors(x - y): if (a, k) in precalc[x]: continue add_precalc(precalc, x, (a, k), 2, res, N) for step, count in precalc[x].iteritems(): count += 1 if count > res[1]["count"]: res = (step, {"end":x, "count":count}) add_precalc(precalc, x, step, count, res, N) precalc[x] = None d = [res[1]["end"]] for x in range(res[1]["count"] - 1, 0, -1): d.append(d[-1] - res[0][0] * res[0][1] ** x) d.reverse() return d` `

• 遍历数组
• 对于数组中的每个前一个元素，计算当前元素和前一个元素之间差异的因子，然后预先计算序列的下一个可能元素，并将其保存到预分析数组
• 所以当到达元素`i` ，在precalc数组中已经有了元素`i`所有可能的序列，所以我们必须计算下一个可能的元素并将其保存到precalc中。

• 更有效的分解algorithm
• find一种方法，不要在数组的每个元素上看到，使用数组sorting的事实，并且已经有一个预先计算好的序列

python：

` `def subseq(a): seq = [] aset = set(a) for i, x in enumerate(a): # elements after x for j, x2 in enumerate(a[i+1:]): j += i + 1 # enumerate starts j at 0, we want a[j] = x2 bk = x2 - x # b*k (assuming k and k's exponent start at 1) # given b*k, bruteforce values of k for k in range(1, bk + 1): items = [x, x2] # our subsequence so far nextdist = bk * k # what x3 - x2 should look like while items[-1] + nextdist in aset: items.append(items[-1] + nextdist) nextdist *= k if len(items) > len(seq): seq = items return seq` `

• 宽度和高度等于它的超级查看使用自动布局编程？
• 我如何反映dynamic对象的成员？
• 静态内存分配和dynamic内存分配之间的区别
• 如何在Javascript中调用dynamic命名的方法？
• 用reflection调用静态方法
• 静态数组与C ++中的dynamic数组
• JavaScript的 - 基于select更改表单操作？
• MySQLdynamic透视
• Xcode 6 iOS创build一个Cocoa Touch框架 - 体系结构问题
• replaceXML文件中的dynamic内容
• 使用JavaScript / jQuery即时修改CSS类属性值