#CS50602. 完善程序6-搜索算法-2寻找等差数列
完善程序6-搜索算法-2寻找等差数列
(寻找等差数列)
有一些长度相等的等差数列(数列中每个数都为 0∼59 的整数),设长度均为 L,将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数,问原先,L 最大可能为多大?先读入一个数 n(1≤n≤60),再读入 n 个数,代表打乱后的数。输出等差数列最大可能长度 L。
#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now) {
int first, second, delta, i;
int ok;
while ( ① && !hash[now])
++now;
if (now > maxnum)
return 1;
first = now;
for (second = first; second <= maxnum; second++)
if (hash[second]) {
delta = ② ;
if (first + delta * ③ > maxnum)
break;
if (delta == 0)
ok = ( ④ );
else{
ok = 1;
for (i = 0; i < ans; i++)
ok = ⑤ && (hash[first+delta*i]);
}
if (ok){
for (i = 0; i < ans; i++)
hash[first+delta*i]--;
if (work(first))
return 1;
for (i = 0; i < ans; i++)
hash[first+delta*i]++;
}
}
return 0;
}
int main(){
int i;
memset(hash, 0, sizeof(hash));
cin >> n;
maxnum = 0;
for (i = 0; i < n; i++){
cin >> x;
hash[x]++;
if (x > maxnum)
maxnum = x;
}
for (ans = n; ans >= 1; ans--)
if ( n%ans==0 && ⑥ ) {
cout << ans << endl;
break;
}
return 0;
- ①处应填( ){{ select(1) }}
- now<maxnum
- now>=maxnum
- now<=maxnum
- now>maxnum
- ②处应填( ){{ select(2) }}
- second-first
- second
- first-second
- second-ans
- ③处应填( ){{ select(3) }}
- ans-1
- ans-delta
- ans
- ans-first
- ④处应填( ){{ select(4) }}
- hash[first]>ans
- hash[first]>=ans
- hash[first]<=ans
- hash[first]<ans
- ⑤处应填( ){{ select(5) }}
- 0
- (!ok)
- 1
- ok
- ⑥处应填( ){{ select(6) }}
- work(0)
- work(0)<=0
- work(ans)
- (!work(ans))