[还是代码游戏]对折纸 - 编程论坛

#2

fulltimelink2020-04-13 21:05

<< 左移位 , 计算这张纸的最小边长肯定很有意思。

#3

lin51616782020-04-13 21:07

以下是引用fulltimelink在2020-4-13 21:05:07的发言：

<< 左移位 , 计算这张纸的最小边长肯定很有意思。

可以但显然不是最苛刻的做法
穷极一切可能的缩进循环次数

#4

wmf20142020-04-13 21:17

(int)(log(88484300)/log(2))+1

#5

fulltimelink2020-04-13 21:17

回复 3楼 lin5161678

嗯，对，再加上分治，应该会好些

#6

lin51616782020-04-13 21:20

以下是引用wmf2014在2020-4-13 21:17:37的发言：

(int)(log(88484300)/log(2))+1

估计你的意思其实是 (int)log2(88484300) + 1
是对的但表达式写得繁琐了点

#7

lin51616782020-04-13 21:21

以下是引用fulltimelink在2020-4-13 21:17:56的发言：

嗯，对，再加上分治，应该会好些

不是很明白你所说的分治
能详细解说一下吗?

#8

wmf20142020-04-13 21:22

log2编译不成功。

#9

fulltimelink2020-04-13 21:23

回复 7楼 lin5161678

就是桶排序用的那个分治思想，折半或者放大

#10

wmf20142020-04-13 21:27

当然也可以右移到负数，循环5次，结果是32-5即可。
for(i=88484300;i>0;j++,i*=2);
printf("%d\n",32-j);
还有一个快速去2位底的对数函数，这是网上^v的
int FastLog2(int x)
{
    float fx;
    unsigned long ix, exp;

    fx = (float)x;
    ix = *(unsigned long*)&fx;
    exp = (ix >> 23) & 0xFF;

    return exp - 127;
}

#11

return_02020-04-13 21:27

快速幂行么.。。

#12

return_02020-04-13 21:30

17次，最笨的算法都能做到 0.04788 sec

[此贴子已经被作者于2020-4-13 21:37编辑过]

#13

lin51616782020-04-13 21:34

以下是引用wmf2014在2020-4-13 21:22:24的发言：

log2编译不成功。

这就有点奇怪了标准文档ISO/IEC 9899:201x 里面是支持这个函数的

#14

lin51616782020-04-13 21:39

以下是引用wmf2014在2020-4-13 21:27:00的发言：

当然也可以右移到负数，循环5次，结果是32-5即可。
for(i=88484300;i>0;j++,i*=2);
printf("%d\n",32-j);
还有一个快速去2位底的对数函数，这是网上^v的
int FastLog2(int x)
{
    float fx;
    unsigned long ix, exp;

    fx = (float)x;
    ix = *(unsigned long*)&fx;
    exp = (ix >> 23) & 0xFF;

    return exp - 127;
}

for(i=88484300;i>0;j++,i*=2);
printf("%d\n",32-j);

这个做法是目前所有实现中最优秀的做法了
但是有一个小小的瑕疵这个做法利用了有符号数溢出这是一个不可靠的特性
改为无符号类型循环退出条件改为检查最高位是不是1 会更合适一些

对数函数的是目前所有做法里面最快的
但ix = *(unsigned long*)&fx;这一句其实不能保证正确
float* 转换到 unsigned long* 再做一元*是做法我个人不提倡
备注我知道这个做法十分著名但我就是不提倡

#15

return_02020-04-13 21:39

cout改成printf变成了 0.03096 sec 省了0.01692 sec

#16

lin51616782020-04-13 21:40

回复 9楼 fulltimelink

折半是一个十分有价值的想法
但实现起来估计会在边界值碰到很多问题
有不少坑需要解决

#17

D22845814702020-04-13 21:42

请问答案是不是26次？？？

程序代码：

#include<stdio.h>
int main()
{
    double sum = 0;
    double num=0.1;
    int count = 0;
    while (1)
    {
        sum += num;
        num *= 2;
        count++;
        if (sum > 8844430)
        {
            printf("%d\n", count - 1); break;
        }
    }
    return 0;
}

#18

lin51616782020-04-13 21:44

回复 12楼 return_0

17次对比目前已知的折半或者左移88444300
显得略多

#19

lin51616782020-04-13 21:46

以下是引用D2284581470在2020-4-13 21:42:08的发言：

请问答案是不是26次？？？

#include<stdio.h>
int main()
{
    double sum = 0;
    double num=0.1;
    int count = 0;
    while (1)
    {
        sum += num;
        num *= 2;
        count++;
        if (sum > 8844430)
        {
            printf("%d\n", count - 1); break;
        }
    }
    return 0;
}

27次
你的count不应该 -1
因为对折1次之后就是0.2mm了

#20

return_02020-04-13 21:48

改成位运算更慢了

#21

lin51616782020-04-13 21:58

以下是引用return_0在2020-4-13 21:48:01的发言：

改成位运算更慢了

很好奇的你的修改和测试方式
另外需要说的是
你把输出也算到计时里面的做法其实不对
这个算法不包括输出
输出只是一个验证
计算算法消耗时间你计算循环次数就差不多了

#22

fulltimelink2020-04-14 08:20

回复 16楼 lin5161678

是的，准备写个测试下。昨天又复习了下浮点数存储... “高级语言”写多了，以前的都忘了，全还给老师了。。。

#23

return_02020-04-14 08:57

递归行不行

#24

lin51616782020-04-14 09:01

回复 23楼 return_0

递归还是循环在这里影响不大
都差不多