[已解决]数据结构初学者求大佬解答猜数字算法

1113753663

猜测一个1000以内的数字，怎么设计算法可以让猜的次数最少，用c语言哦，球球了

最佳答案

月排行榜 / 总排行榜

人造人

2022-3-4 13:16:53

1113753663 发表于 2022-3-4 14:27
我们刚开始这个课，都不会数据结构呢，老师就是让我们自己编一个c语言的程序来测试次数，谢谢大佬

如果数据是有序的话，二分搜索的效率是最好的，因为一次测试就可以排除掉一半的数据
像下面这样夸张的数据，也用不了几次就能找到

$ cat main.c
#include <stdio.h>

void guess(size_t value, size_t min, size_t max) {
    size_t current = (min + max) / 2;
    printf("-> %lu\n", current);
    if(current == value) return;
    if(current > value) guess(value, min, current);
    else guess(value, current, max);
}

int main(void) {
    size_t value;
    scanf("%lu", &value);
    guess(value, 0, 1000000000000000001);
    return 0;
}
$ gcc-debug -o main main.c
$ ./main
500
-> 500000000000000000
-> 250000000000000000
-> 125000000000000000
-> 62500000000000000
-> 31250000000000000
-> 15625000000000000
-> 7812500000000000
-> 3906250000000000
-> 1953125000000000
-> 976562500000000
-> 488281250000000
-> 244140625000000
-> 122070312500000
-> 61035156250000
-> 30517578125000
-> 15258789062500
-> 7629394531250
-> 3814697265625
-> 1907348632812
-> 953674316406
-> 476837158203
-> 238418579101
-> 119209289550
-> 59604644775
-> 29802322387
-> 14901161193
-> 7450580596
-> 3725290298
-> 1862645149
-> 931322574
-> 465661287
-> 232830643
-> 116415321
-> 58207660
-> 29103830
-> 14551915
-> 7275957
-> 3637978
-> 1818989
-> 909494
-> 454747
-> 227373
-> 113686
-> 56843
-> 28421
-> 14210
-> 7105
-> 3552
-> 1776
-> 888
-> 444
-> 666
-> 555
-> 499
-> 527
-> 513
-> 506
-> 502
-> 500
$

跳转到最佳答案楼层

人造人

1113753663 发表于 2022-3-4 14:27
我们刚开始这个课，都不会数据结构呢，老师就是让我们自己编一个c语言的程序来测试次数，谢谢大佬

如果数据是有序的话，二分搜索的效率是最好的，因为一次测试就可以排除掉一半的数据
像下面这样夸张的数据，也用不了几次就能找到

$ cat main.c
#include <stdio.h>

void guess(size_t value, size_t min, size_t max) {
    size_t current = (min + max) / 2;
    printf("-> %lu\n", current);
    if(current == value) return;
    if(current > value) guess(value, min, current);
    else guess(value, current, max);
}

int main(void) {
    size_t value;
    scanf("%lu", &value);
    guess(value, 0, 1000000000000000001);
    return 0;
}
$ gcc-debug -o main main.c
$ ./main
500
-> 500000000000000000
-> 250000000000000000
-> 125000000000000000
-> 62500000000000000
-> 31250000000000000
-> 15625000000000000
-> 7812500000000000
-> 3906250000000000
-> 1953125000000000
-> 976562500000000
-> 488281250000000
-> 244140625000000
-> 122070312500000
-> 61035156250000
-> 30517578125000
-> 15258789062500
-> 7629394531250
-> 3814697265625
-> 1907348632812
-> 953674316406
-> 476837158203
-> 238418579101
-> 119209289550
-> 59604644775
-> 29802322387
-> 14901161193
-> 7450580596
-> 3725290298
-> 1862645149
-> 931322574
-> 465661287
-> 232830643
-> 116415321
-> 58207660
-> 29103830
-> 14551915
-> 7275957
-> 3637978
-> 1818989
-> 909494
-> 454747
-> 227373
-> 113686
-> 56843
-> 28421
-> 14210
-> 7105
-> 3552
-> 1776
-> 888
-> 444
-> 666
-> 555
-> 499
-> 527
-> 513
-> 506
-> 502
-> 500
$

人造人

数据结构？这需要数据结构吗？

#include <stdio.h>

void guess(size_t value, size_t min, size_t max) {
    size_t current = (min + max) / 2;
    printf("-> %lu\n", current);
    if(current == value) return;
    if(current > value) guess(value, min, current);
    else guess(value, current, max);
}

int main(void) {
    /*
    size_t value;
    scanf("%lu", &value);
    guess(value, 0, 1001);
    */
    for(size_t i = 0; i <= 1000; ++i) {
        printf("%lu\n", i);
        guess(i, 0, 1001);
    }
    return 0;
}

人造人

哦，没认真看题，题目没有说要数据结构
算法用二分搜索
就是每一次都尝试目标方向的一半位置，逐渐靠近目标，直到和目标重叠

1113753663

人造人 发表于 2022-3-4 14:15
哦，没认真看题，题目没有说要数据结构
算法用二分搜索
就是每一次都尝试目标方向的一半位置，逐渐靠近目 ...

我们刚开始这个课，都不会数据结构呢，老师就是让我们自己编一个c语言的程序来测试次数，谢谢大佬

1113753663

我自己也写了个，可以帮忙看一下吗#include <stdio.h>

int main()

{

    int i,j,num;

    scanf("%d",&num);

    for (j=1000,i=0;num!=0;j=j/2)

    {

        num=num-j;

        if (num<0)

        {

            num=num+j;

            continue;

        }

        i++;

    }

    printf("%d",i);

    return 0;

}

人造人

1113753663 发表于 2022-3-4 14:40
我自己也写了个，可以帮忙看一下吗#include

int main()

1. 回复别人要点 “回复” 按钮
这也就是我为什么5个小时不理你的原因，因为我根本就不知道你回复了我
2. num不是要查找的那个值吗？
你怎么能把这个值给改了呢？改了这个值，那之后还怎么查找这个值？
num=num-j;
你是如何实现这个查找的，你这个代码的思路是怎样的？

1113753663

人造人 发表于 2022-3-4 19:57
1. 回复别人要点 “回复” 按钮
这也就是我为什么5个小时不理你的原因，因为我根本就不知道你回复了我
...

不好意思啊，我刚接触这个没点回复，这个题是算次数的不是求那个值的，就比如540这个数是自己输入的然后看程序运行几次可以把这个数猜出来，主要是看次数的，我的思路就是给num一个值然后通过依次递减，当num等于0时，循环结束输出i值，在减的过程中num可能会小于j所以加了一个if判断，如果小的话这一次就不能算，所以直接continue，i++也没有放在for语句中，您给的二分法我们还没学到 不过第一个挺好的，给你点赞

人造人

1113753663 发表于 2022-3-4 21:23
不好意思啊，我刚接触这个没点回复，这个题是算次数的不是求那个值的，就比如540这个数是自己输入的然后 ...

不知道你在说什么，像我下面这样说明你代码的思路

1000太大不方便举例，这里用100举例子
在100之内猜
要猜的这个数字这里就拿37举例
第1次猜 50
就是 (0 + 100) / 2
因为 37 < 50
(0 + 50) / 2
所以第2次猜 25
37 > 25
(25 + 50) / 2
第3次猜37

人造人

1113753663 发表于 2022-3-4 21:23
不好意思啊，我刚接触这个没点回复，这个题是算次数的不是求那个值的，就比如540这个数是自己输入的然后 ...

如果要你在100之内猜37，你要如何做？先猜哪个数？然后猜哪个数？然后呢？
我这里先猜50，然后猜25，然后猜37
用了3次
你的代码先猜的是哪个数？第2次猜的是哪个？第3次猜哪个？

1113753663

人造人 发表于 2022-3-4 22:46
如果要你在100之内猜37，你要如何做？先猜哪个数？然后猜哪个数？然后呢？
我这里先猜50，然后猜25， ...

比如吧，你猜459
第一次：459-500=num<0；所以再让num加上500；
第二次：500/2=250；然后用459-250=209；
第三次：250/2=125；然后用209-125=84；
第四次：125/2=62；然后用84-62=22；
第五次：62/2=31；22-31<0；用if判断num<0；所以num再加上31成为22；
第六次：31/2=15；22-15=7；
第七次：15/2=7；7-7=0;此时num=0循环结束输出i；
这是我的思路但是代码好像是不对的；而且某些数字猜不出来

人造人

1113753663 发表于 2022-3-5 13:47
比如吧，你猜459
第一次：459-500=num

你第1次猜的多少？ 500 ？
第2次猜的 250 ？
第3次猜 125
第4次猜 62
第5次猜 31
第6次猜 15
第7次猜 7
第8次呢？
让你猜的是459，又不是7,怎么不继续猜了？
这是什么奇怪的方法，完全没见过

人造人

人造人 发表于 2022-3-5 15:18
你第1次猜的多少？ 500 ？
第2次猜的 250 ？
第3次猜 125

你可以这样猜
第一次猜19
第二次猜870
第三次猜123
第四次猜777
第五次猜459
猜中了，一共用了5次
你的呢？你用了7次是吧
第一次猜的哪个数字？
第二次猜的哪个数字？
第三次猜的哪个数字？
。。。
让你猜的是 459，这和7 - 7 = 0 有什么关系？
你最后猜的是7，又不是459，为什么不继续猜了？

1113753663

人造人 发表于 2022-3-5 15:25
你可以这样猜
第一次猜19
第二次猜870

可能我的理解不对吧，我想着就是一步步把要猜的数字减到0；
要猜的那个数字是自己输入的所以代码里面有scanf，
我们这个作业就是把代码给老师，老师自己输入一个数
看程序可以几次猜出这个数，比如老师输入459，最后减到0了。
不就证明这个数被猜出来了吗？

人造人

1113753663 发表于 2022-3-5 16:34
可能我的理解不对吧，我想着就是一步步把要猜的数字减到0；
要猜的那个数字是自己输入的所以代码里面有s ...

我不知道如何给你解释了，总之就是你的方法错的离谱
最后减到0了。不就证明这个数被猜出来了吗
你能告诉我，你每一次猜的那个数是多少吗？

人造人

1113753663 发表于 2022-3-5 16:34
可能我的理解不对吧，我想着就是一步步把要猜的数字减到0；
要猜的那个数字是自己输入的所以代码里面有s ...

猜出来是什么意思？
猜出来就是你程序给出的那个数字和用户输入的那个数字一样

1113753663

人造人 发表于 2022-3-5 17:22
猜出来是什么意思？
猜出来就是你程序给出的那个数字和用户输入的那个数字一样

https://qingyun.schoolhug.club/static/alipay/
这是我们老师给的一个网页，你可以看一下，我的描述可能有问题；
我们的目的就是猜出最后的数字，
每一次减都相当于往里面充钱，等冲到不能再充值的时候不就是num=0的时候吗

人造人

1113753663 发表于 2022-3-6 09:55
https://qingyun.schoolhug.club/static/alipay/
这是我们老师给的一个网页，你可以看一下，我的描述可 ...

还是没有看明白你的程序，像下面这样描述一下你的代码逻辑
我在调试这个程序的时候，发现了两个问题
你检查一下，看看是不是你的代码中也是这个问题

$ cat main.c
#include <stdio.h>

void guess(size_t value, size_t min, size_t max) {
    size_t i = 0;
    while(value) {
        size_t current = (min + max) / 2;
        //++current;      // 最后会出现0的情况，这直接导致死循环，所以要加1
        //直接加1还是不行，会出现value是1，current是2的情况，这也导致死循环
        if(!current) ++current;
        printf("第%lu次尝试, 目标是%lu, 当前要存储的数是%lu, ", i++, value, current);
        if(current > value) {
            printf("存储失败\n");
        } else {
            printf("存储成功\n");
            value -= current;
        }
        max = current;
    }
}

int main(void) {
    size_t value;
    scanf("%lu", &value);
    guess(value, 0, 1001);
    /*
    for(size_t i = 0; i <= 1000; ++i) {
        guess(i, 0, 1001);
        printf("====================\n");
    }
    */
    return 0;
}
$ gcc-debug -o main main.c
$ ./main
37
第0次尝试, 目标是37, 当前要存储的数是500, 存储失败
第1次尝试, 目标是37, 当前要存储的数是250, 存储失败
第2次尝试, 目标是37, 当前要存储的数是125, 存储失败
第3次尝试, 目标是37, 当前要存储的数是62, 存储失败
第4次尝试, 目标是37, 当前要存储的数是31, 存储成功
第5次尝试, 目标是6, 当前要存储的数是15, 存储失败
第6次尝试, 目标是6, 当前要存储的数是7, 存储失败
第7次尝试, 目标是6, 当前要存储的数是3, 存储成功
第8次尝试, 目标是3, 当前要存储的数是1, 存储成功
第9次尝试, 目标是2, 当前要存储的数是1, 存储成功
第10次尝试, 目标是1, 当前要存储的数是1, 存储成功
$ ./main
859
第0次尝试, 目标是859, 当前要存储的数是500, 存储成功
第1次尝试, 目标是359, 当前要存储的数是250, 存储成功
第2次尝试, 目标是109, 当前要存储的数是125, 存储失败
第3次尝试, 目标是109, 当前要存储的数是62, 存储成功
第4次尝试, 目标是47, 当前要存储的数是31, 存储成功
第5次尝试, 目标是16, 当前要存储的数是15, 存储成功
第6次尝试, 目标是1, 当前要存储的数是7, 存储失败
第7次尝试, 目标是1, 当前要存储的数是3, 存储失败
第8次尝试, 目标是1, 当前要存储的数是1, 存储成功
$ ./main
430
第0次尝试, 目标是430, 当前要存储的数是500, 存储失败
第1次尝试, 目标是430, 当前要存储的数是250, 存储成功
第2次尝试, 目标是180, 当前要存储的数是125, 存储成功
第3次尝试, 目标是55, 当前要存储的数是62, 存储失败
第4次尝试, 目标是55, 当前要存储的数是31, 存储成功
第5次尝试, 目标是24, 当前要存储的数是15, 存储成功
第6次尝试, 目标是9, 当前要存储的数是7, 存储成功
第7次尝试, 目标是2, 当前要存储的数是3, 存储失败
第8次尝试, 目标是2, 当前要存储的数是1, 存储成功
第9次尝试, 目标是1, 当前要存储的数是1, 存储成功
$ ./main
789
第0次尝试, 目标是789, 当前要存储的数是500, 存储成功
第1次尝试, 目标是289, 当前要存储的数是250, 存储成功
第2次尝试, 目标是39, 当前要存储的数是125, 存储失败
第3次尝试, 目标是39, 当前要存储的数是62, 存储失败
第4次尝试, 目标是39, 当前要存储的数是31, 存储成功
第5次尝试, 目标是8, 当前要存储的数是15, 存储失败
第6次尝试, 目标是8, 当前要存储的数是7, 存储成功
第7次尝试, 目标是1, 当前要存储的数是3, 存储失败
第8次尝试, 目标是1, 当前要存储的数是1, 存储成功
$

1113753663

人造人 发表于 2022-3-6 22:20
还是没有看明白你的程序，像下面这样描述一下你的代码逻辑
我在调试这个程序的时候，发现了两个问题
你 ...

谢谢了，这个就是我想要的哪一种

人造人

1113753663 发表于 2022-3-7 08:16
谢谢了，这个就是我想要的哪一种

7                num = num - j;
1: {i, j, num} = {3, 0, 2}

就是我说的那种情况，这里的j成0了，这样下去不管循环多少次都不可能成2

还有，把代码写好

#include <stdio.h>

int main(void) {
    int i, j, num;
    scanf("%d", &num);
    for(j = 1000, i = 0; num != 0; j = j / 2) {
        if(!j) ++j;     // j是0的时候强制改成1
        num = num - j;
        if(num < 0) {
            num = num + j;
            continue;
        }
        i++;
    }
    //printf("%d", i);
    printf("%d\n", i);
    return 0;
}