我正在练习2023 年英国信息学奥林匹克竞赛试卷的
在斐波那契数列中,每个数字都是通过将序列中的前两个数字相加而生成的。我们从数字 1 和 2 开始,因此序列为 1、2、3、5、8、13、21、34、55、89……数字 n 的泽肯多夫表示由斐波那契数列中的不同数字组成,这些数字的总和为 n,其中斐波那契数列中没有使用两个相邻的数字。始终有一个唯一的表示。
例如:
- 21 用单个数字 21 来表示;
- 21 不能用 8 13 来表示,即使它们之和为 21,因为这些数字在斐波那契数列中是相邻的;
- 100 表示为 3 8 89
n 的 Zeckendorf 表示始终包含不大于 n 的斐波那契数列中的最大数字。
编写一个程序,读取一个数字(介于 1 和 1,000,000 之间,包括 1 和 1,000,000),并以相应的 Zeckendorf 表示形式输出该数字(以任意顺序)。
我写了这段代码:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;
int find_largest_le_fib_n(int n) {
if (n == 0 || n == 1) {
return n;
}
int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
Node* find_zeckendorf(int n) {
Node *last;
Node *first;
Node *penultimate = NULL;
int largest_le_fib;
while (n > 0) {
largest_le_fib = find_largest_le_fib_n(n);
last = malloc(sizeof(Node));
last->data = largest_le_fib;
last->next = NULL;
if (first == NULL) {
first = last;
}
if (penultimate != NULL) {
penultimate->next = last;
}
penultimate = last;
n -= largest_le_fib;
}
return first;
}
int main() {
int n = 0;
printf("Enter number: ");
scanf("%d", &n);
Node *zeckendorf_list = find_zeckendorf(n);
while (zeckendorf_list != NULL) {
printf("%d ", zeckendorf_list->data);
Node *temp = zeckendorf_list;
zeckendorf_list = zeckendorf_list->next;
free(temp);
}
printf("\n");
}
示例运行:
Enter number: 100
89 8 3
(更多测试用例可在中找到)
我将非常高兴听到关于此代码的任何改进。
\endgroup
1
最佳答案
2
-
Node *first;
应为Node *first = NULL;
。否则, 的测试将first == NULL
调用 UB。 -
find_largest_le_fib_n
就是一遍又一遍地重复同样的工作。似乎最好预先计算1,000,000
一次范围内的斐波那契数列,然后对其进行二分搜索。你甚至可以离线进行——它们的数量并不太多。 -
malloc
可能会失败。请务必测试其返回值。 -
问题陈述未指定表示中的数字顺序。例如
3 8 89
, ,而您的代码生成89 8 3
。如果这样的顺序没问题,则根本不需要链接列表。
\endgroup
5
-
\begingroup
如果不在链接列表中,您建议如何存储数字?
\endgroup
– -
\begingroup
@sbottingota 由于您发布的问题陈述表明“按任意顺序”,因此无需存储发现的数字。只需按发现的顺序输出每个数字,然后继续…
\endgroup
– -
\begingroup
@Fe2O3 我知道,但是由于问题 1b-1d 也与 zeckendorf 表示有关,因此我不想立即将它们打印到标准输出。除了链接列表之外,您知道还有其他方法吗?
\endgroup
–
-
\begingroup
@sbottingota 刚刚发布了我自己的答案(您的代码版本),并提到只有 31 个 Fib 数字,最大可达 10^6。这是一个需要一次性填充的小数组,并且“选定”的值可以复制到更小的数组中(连续),这显然……如果您想解决其他部分(“b”-“d”),那么您将不得不找到另一个解决方案53,316,291,173
。考虑一下,LL 节点除了数据之外,还需要每个指针 8 个字节。建议您阅读有关realloc()
以较大的增量增加数组的信息,但仅在需要时才增加……
\endgroup
– -
\begingroup
@sbottingota FWIW:该数字(53,316,291,173
)是 Fib #54(基于 0、1、1、…)。比我预期的要小得多!建议用 54 个值填充一个数组,然后简单地扫描它,这将是有利的。(如果你真的很聪明,你也许能够推导出一个公式,预测每个值的Zeckendorf 表示需要多少个项…研究有关该主题的维基百科页面;特别是页面右上角的图表…干杯!
\endgroup
–
|
审查:
再次强调,代码看起来不错,可以完成预期的任务。呈现得非常好,而且相当容易理解。赞!
但是,练习指出“按任何顺序”,因此处理堆内存和链接列表的大部分文书代码(也是正确的)实际上是一种干扰。
由于练习仅生成数字列表,因此这里提供以下内容(从您的代码中提炼)供您学习和评估。
#include <stdio.h>
int find( int n ) {
if( n == 1 ) return n;
int f1 = 1, f2 = 2; // tiny shortcut as problem suggests
while( f1 + f2 <= n ) {
int fx = f1 + f2;
f1 = f2;
f2 = fx;
}
return f2;
}
int main( void ) {
int n = 0;
for( ;; ) { // infinite loop for testing many numbers
printf("Enter number: ");
if( scanf( "%d", &n ) != 1 ) { // check return codes!
scanf( "%*[^\n]" ); // clear the input buffer. (read scanf doco!)
continue;
}
for( int large; n; n -= large )
printf( "%d ", large = find( n ) ); // output is all that's required
puts( "" );
}
return 0;
}
以下是一些斐波那契数列的简略列表
0 #01
1 #02
...
832040 #31
1346269 #32 // Bigger than the problem's 1000000 limit
输出:
Enter number: 832039
514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2
Enter number:
现在我们知道 0 到 1000000 之间有 31 个斐波那契数,一个简单的数组int store[31]
就足以存储和打印本练习中感兴趣的值。
如果这样的数组在启动时被填充一次(仅限于“单次”感兴趣的限制或多次查询的 1000000 限制),那么确定要打印的Zeckendorf 表示值的速度将大大加快。
你的代码写得非常好。一个对未来有价值的教训是只编写正确的代码来满足今天的需求。有些人建议以某些(昂贵的)方式编码“以防明天需求发生变化”。让明天自己照顾自己吧。注意不要让用户输入"foo"
而不是15642
导致你的程序崩溃。
\endgroup
2
-
1\begingroup
也许if( scanf( "%d", &n ) != 1 ) {
–>if( scanf( "%d", &n ) != 1 || n <= 0 ) {
(带有错误消息)不仅可以处理非数字输入,还可以处理超出范围(至少在范围的一侧)。照原样,仅'\n'
在输入时才打印代码0
。
\endgroup
–
-
\begingroup
@chux-ReinstateMonica 是的,我在这里提供的代码有很多可以改进的地方。谢谢。我的主要目的是删除 LL 位,防止输入"foobar"
,并“发布”可以快速计算、存储和搜索的斐波那契数的(微小)计数……OP 似乎也对原始挑战的其他部分感兴趣……SO 和 CR 之间的界限变得模糊!!:-)
干杯!
\endgroup
–
|
您认为哪一个更容易审查正确性:
last = malloc(sizeof(Node));
或last = malloc(sizeof *last);
?\endgroup
–
|