3n+1数列问题

时间:2023-01-25 09:57:22

3n+1数列问题

Time Limit: 1000MS Memory Limit: 65536KB

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

Hint

代码如下:

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