3n+1数列问题

淡淡的烟草味﹌ 2022-07-11 04:25 114阅读 0赞

#### 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 ####

输出链表序列

#### Example Input ####

10 5

#### Example Output ####

2 4 8 5 16

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