#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;
  1. ①处应填( ){{ select(1) }}
  • now<maxnum
  • now>=maxnum
  • now<=maxnum
  • now>maxnum
  1. ②处应填( ){{ select(2) }}
  • second-first
  • second
  • first-second
  • second-ans
  1. ③处应填( ){{ select(3) }}
  • ans-1
  • ans-delta
  • ans
  • ans-first
  1. ④处应填( ){{ select(4) }}
  • hash[first]>ans
  • hash[first]>=ans
  • hash[first]<=ans
  • hash[first]<ans
  1. ⑤处应填( ){{ select(5) }}
  • 0
  • (!ok)
  • 1
  • ok
  1. ⑥处应填( ){{ select(6) }}
  • work(0)
  • work(0)<=0
  • work(ans)
  • (!work(ans))