gpt4 book ai didi

c - 《Algorithms in C part 1-4》p172 shellSort中的for(h=1;h<=(r-1)/9;h=h*3+1)循环是什么意思?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:58:41 26 4
gpt4 key购买 nike

我正在研究来自 Sedgewick 的 Shell 排序 Algorithms in C part 1-4在第 172 页。

我使用 size (数组的长度),而不是 lr (开始和结束);所以我的代码是

int i,j,h;
int key;
for( h=1;h<=(size-1)/9;h=h*3+1);
for(;h>0;h/=3)
{
for(i=h;i<size;i++)
{
key=num[i];
j=i;
while(j>=h&&key>num[j-h];j-=h)
{
num[j]=num[j-h];
}
num[j]=key;
}
}

这些我都知道。我读了TAOCP .我知道 1, 4, 13, … 是最好的序列(可比)。但是在这个位置,我的代码有

for(h=1;h<size;h=h*3+1);

我的问题是:他为什么写h<(size-1)/9

' /9 是什么意思? '是什么意思?

最佳答案

循环:

for (h = 1; h < size; h = h * 3 + 1)
;

大多数时候超过数组的大小。替代循环将间隙保持在范围内。

您可以通过像这样的简单测试程序亲眼看到这一点:

#include <stdio.h>

static inline int hs_gap9(int size)
{
int h;
for (h = 1; h <= (size - 1) / 9; h = h * 3 + 1)
;
return h;
}

static inline int hs_gap3(int size)
{
int h;
for (h = 1; h < size; h = h * 3 + 1)
;
return h;
}

int main(void)
{
for (int i = 1; i < 100; i++)
printf("Size: %3d; gap9 = %d; gap3 = %d\n", i, hs_gap9(i), hs_gap3(i));
return 0;
}

示例输出:

Size:   1; gap9 =   1; gap3 =   1
Size: 2; gap9 = 1; gap3 = 4
Size: 3; gap9 = 1; gap3 = 4
Size: 4; gap9 = 1; gap3 = 4
Size: 5; gap9 = 1; gap3 = 13
Size: 6; gap9 = 1; gap3 = 13
Size: 7; gap9 = 1; gap3 = 13
Size: 8; gap9 = 1; gap3 = 13
Size: 9; gap9 = 1; gap3 = 13
Size: 10; gap9 = 4; gap3 = 13
Size: 11; gap9 = 4; gap3 = 13
Size: 12; gap9 = 4; gap3 = 13
Size: 13; gap9 = 4; gap3 = 13
Size: 14; gap9 = 4; gap3 = 40
Size: 15; gap9 = 4; gap3 = 40
Size: 16; gap9 = 4; gap3 = 40

Size: 34; gap9 = 4; gap3 = 40
Size: 35; gap9 = 4; gap3 = 40
Size: 36; gap9 = 4; gap3 = 40
Size: 37; gap9 = 13; gap3 = 40
Size: 38; gap9 = 13; gap3 = 40
Size: 39; gap9 = 13; gap3 = 40
Size: 40; gap9 = 13; gap3 = 40
Size: 41; gap9 = 13; gap3 = 121
Size: 42; gap9 = 13; gap3 = 121
Size: 43; gap9 = 13; gap3 = 121

Size: 97; gap9 = 13; gap3 = 121
Size: 98; gap9 = 13; gap3 = 121
Size: 99; gap9 = 13; gap3 = 121

如您所见,'gap3' 算法返回 h 的初始值,该值大于数组的大小。 'gap9' 算法返回 h 的初始值,该值小于数组的大小。这在循环上节省了一点开销(节省了外循环的一次迭代,其中中间循环在第一个循环退出而不触及内循环。

关于c - 《Algorithms in C part 1-4》p172 shellSort中的for(h=1;h<=(r-1)/9;h=h*3+1)循环是什么意思?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27914025/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com