3n+1数列问题

Bertha 。 2022-05-13 10:16 117阅读 0赞

### 3n+1数列问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

有一天小标遇到了经典的3n+1数链问题，他想知道3n+1数链的前k个数是多少。  
下面小标来给你介绍一下3n+1数链是什么，  
给定一个数n，如果n为偶数，那么下一个数n1 = n / 2;否则n1 = 3 \* n + 1;  
如果n1为偶数，那么下一个数n2 = n1 / 2;否则n2 = 3 \* n1 + 1;  
如果n2为偶数，那么下一个数n3 = n2 / 2;否则n3 = 3 \* n2 + 1;  
.....  
小标最近刚刚学习了链表，他想把这两个知识结合一下，所以，他想按照下面的规定去做。  
①起始n为10，k为5，链表为空  
②判断n为偶数，他会往链表头部加一个5（即n/2），此时链表中序列为5，n变为5 -> NULL  
③接下来n==5，判断n为奇数，他会往链表尾部加一个16(即3\*n+1),此时链表中序列为5 -> 16 -> NULL  
④接下来n==16，判断n为偶数，他会往链表头部加一个8(即n/2),此时链表中序列为8 -> 5 -> 16 -> NULL  
⑤接下来n==8，判断n为偶数，他会往链表头部加一个4(即n/2),此时链表中序列为4 - > 8 - > 5 -> 16 -> NULL  
⑥接下来n==4，判断n为偶数，他会往链表头部加一个2(即n/2),此时链表中序列为2 - > 4 - > 8 - > 5 -> 16 -> NULL  
到此时，小标得到了前k个数，那么输出这个序列。  
Ps: 为了变得更容易理解，简单来说就是n为偶数，加在链表头部，n为奇数，加在链表尾部

Input

多组输入。  
对于每组数据，每行两个整数1 <= n , k <= 1000，含义如上

Output

输出链表序列

Sample Input

10 5

Sample Output

2 4 8 5 16

Hint

Source

2015级《程序设计基础II》计科软件通信期末上机考试2

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    int main()
    {
        struct node *head, *tail, *p, *q;
        int n, num, k;
        while(scanf("%d%d", &n, &k) != EOF)
        {
            head = (struct node *)malloc(sizeof(struct node));
            tail = (struct node *)malloc(sizeof(struct node));
            head->next = NULL;
            num = 1;
            if(n % 2 == 0 && num == 1)
            {
                p = (struct node *)malloc(sizeof(struct node));
                p->data = n / 2;
                head->next = p;
                p->next = NULL;
                num = 2;
                n = n / 2;
            }
            if(n % 2 == 1 && num == 1)
            {
                p = (struct node *)malloc(sizeof(struct node));
                p->data = 3 * n + 1;
                head->next = p;
                p->next = NULL;
                num = 2;
                n = 3 * n + 1;
            }
            k = k - 1;
            tail = p;
            while(k--)
            {
                if(n % 2 == 0)
                {
                    q = (struct node *)malloc(sizeof(struct node));
                    q->data = n / 2;
                    q->next = head->next;
                    head->next = q;
                    n = n / 2;
                }
                else
                {
                    q = (struct node *)malloc(sizeof(struct node));
                    q->data = n * 3 + 1;
                    q->next = NULL;
                    tail->next = q;
                    tail = q;
                    n = n * 3 + 1;
                }
            }
            for(p = head->next; p ->next != NULL; p = p->next)
            {
                printf("%d ", p->data);
            }
            printf("%d\n", p->data);
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2559/pid/3535.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2559/pid/3535.html