这题做第二遍的时候，没有第一遍那么顺利。。。
有目录~
C 25’/25’
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int num[MAX], key[MAX], covered[MAX * MAX];
int key_count = 0; //关键数的个数
int cov_count = 0; //covered中的，即覆盖他数的数的个数
int comp(const void *a, const void *b)
{
int *aa = (int *)a;
int *bb = (int *)b;
if(*aa > *bb)
{
return 1;
}
else if(*aa < *bb)
{
return -1;
}
else
{
return 0;
}
}
int n_in_covered(int n)
{
int low, high, mid;
if(cov_count == 0)
{
return 0;
}
low = 0;
high = cov_count - 1;
qsort(covered,cov_count,sizeof(covered[0]),comp);
while(low <= high)
{
mid = (low + high) / 2;
if(n < covered[mid])
{
high = mid - 1;
}
else if(n > covered[mid])
{
low = mid + 1;
}
else if(n == covered[mid])
{
return 1; //在covered中找到了n
}
}
return 0;
}
int even(int n)
{
return n / 2;
}
int odd(int n)
{
return (3 * n + 1) / 2;
}
void callatz(int n)
{
if(!n_in_covered(n)) //n 不再 covered[]中
{
while(n != 1)
{
if(n % 2 == 0)
{
n = even(n);
if(!n_in_covered(n))
{
covered[cov_count++] = n;
}
else
{
break;
}
}
else if(n % 2 != 0)
{
n = odd(n);
if(!n_in_covered(n))
{
covered[cov_count++] = n;
}
else
{
break;
}
}
}
}
}
int main()
{
int K,i;
scanf("%d", &K);
for(i = 0; i < K; i++)
{
scanf("%d",&num[i]);
}
for(i = 0; i < K; i++)
{
callatz(num[i]);
}
for(i = 0; i < K; i++)
{
if(!n_in_covered(num[i])) //num[i] 不在 covered[]中
{
key[key_count++] = num[i];
}
}
qsort(key,key_count,sizeof(key[0]),comp);
for(i = key_count - 1; i >= 0; i--)
{
if(i != key_count - 1)
{
printf(" ");
}
printf("%d",key[i]);
}
return 0;
}
C++
错误代码
先放出错误代码（最下面的代码就是得到全分的代码），因为这个错误代码中的test（有标记出来）部分也算是帮到我的。
代码中有分析。
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;
vector<unsigned> keys;
array<unsigned, 100> test = {};
bool isKey(unsigned x) // 判断是否是关键字
{
vector<unsigned> had = {};
had.push_back(x);
while (x != 1) // 在计算“得到1”的路上，将每一步得到的数字都放入had组中
{
if (0 == x % 2)
{
x = x / 2;
had.push_back(x);
}
else
{
x = (3 * x + 1) / 2;
had.push_back(x);
}
}
// test
for (unsigned item : had)
{
cout << " " << item;
}
cout << "\n";
sort(had.begin(), had.end());
// 检查输入的所有数字 是否都在had组中
for (unsigned item : test)
{
if (!binary_search(had.begin(), had.end(), item))
{
// 一旦“输入的数”中有一个数不在had组中，x就不是关键字
return false;
}
}
return true;
}
int main()
{
unsigned k;
cin >> k;
for (size_t i = 0; i < k; i++)
{
cin >> test[i];
}
// 找关键字
for (size_t i = 0; i < k; i++)
{
if (isKey(test[i]))
{
keys.push_back(test[i]);
}
}
// 排序
sort(keys.rbegin(), keys.rend());
// 输出
for (size_t i = 0; i < keys.size(); i++)
{
if (i)
{
cout << " ";
}
cout << keys[i];
}
return 0;
}
该代码运行结果如下：
对错误代码的分析
运行结果图中，第三行开始，是每个数字“计算得到1”的“轨迹”。
∴对代码做如下修改：
全局范围内建立一个had组，将所有“路径”上的数放入had中，没有被had组中的数覆盖的就是“关键字”。
正确代码 25’/25’
代码开始的部分注释是我对题目的理解以及分析。
/*关键句：“我们称一个数列中的某个数 n 为“关键数”，
如果 n 不能被数列中的其他数字所覆盖。”
一开始认为这句不重要，把题目理解成：一个数x在计算“得到1”的路上，
将每一步得到的数字都放入一个新的had组中，
若had组中包含了所有的“输入的数”，
那么x就是关键字
其实不是：应该是一个或者一个以上的数字——》组成一组数，
这些数合称为“关键字”
解决对策：记录并输出每一个测试用例“在计算 得到1 的路”上得到的数字，
然后找规律、突破口
*/
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;
unsigned k;
vector<unsigned> keys;
vector<unsigned> had;
array<unsigned, 100> test = {};
void getRoad() // 获取“计算得到1”的路径
{
for (size_t i = 0; i < k; i++)
{
unsigned x = test[i];
while (x != 1)
{
if (0 == x % 2)
{
x = x / 2;
had.push_back(x);
}
else
{
x = (3 * x + 1) / 2;
had.push_back(x);
}
}
}
sort(had.begin(), had.end()); // 为了二分查找，比较快
}
int main()
{
cin >> k;
for (size_t i = 0; i < k; i++)
{
cin >> test[i];
}
// 获取“计算得到1”的路径
getRoad();
// 找关键字 没被覆盖的即是关键字
for (size_t i = 0; i < k; i++)
{
if (!binary_search(had.begin(), had.end(), test[i])) // had中没找到，即是没被覆盖
{
keys.push_back(test[i]);
}
}
// 排序
sort(keys.rbegin(), keys.rend());
// 输出
for (size_t i = 0; i < keys.size(); i++)
{
if (i)
{
cout << " ";
}
cout << keys[i];
}
return 0;
}