sdutacm-3n+1数列问题

3n+1数列问题

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

ProblemDescription

有一天小标遇到了经典的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

 输出链表序列

ExampleInput

ExampleOutput

Hint

Author

K
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
//#include<dqeue>
struct node
{

  int data;
  struct node*next;

};
int main()
{

     int n;
     while(~scanf("%d",&n))
     {

        struct node *head;

        head = (struct node*)malloc(sizeof(struct node));
        head->next = NULL;
         struct node *tail = head;
        for(int i=1;i<=n;i++)
        {
            struct node *p = (struct node*)malloc(sizeof(struct node));
            p->next = NULL;
            scanf("%d",&p->data);
            tail->next = p;
            tail = p;

        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
           int kk;
           scanf("%d",&kk);
           if(kk==1)
           {   int num,f = 1;
              scanf("%d",&num);
               tail = head;
               while(tail->next)
               {
                   if(tail->next->data>num)
                   {

                       struct node*u = (struct node*)malloc(sizeof(struct node));
                       u ->data = num;
                       u->next = tail->next;
                       tail ->next = u;
                       f = 0;
                       break;

                   }
                   else tail = tail->next;

               }
               if(f)
               {
                    struct node*u=(struct node*)malloc(sizeof(struct node));
                    u->data = num;
                    u->next =NULL;
                    tail->next = u;

               }




           }
           else if(kk==2)
           {

               int f = 1;
               tail = head;
               while(tail->next)
               {

                 if(f) f = 0;
                 else printf(" ");
                 printf("%d",tail->next->data);
                 tail = tail->next;
               }
               printf("\n");
           }



        }
        while(head)
        {
           tail = head;
           head = head->next;
           free(tail);

        }



     }
   return 0;
}


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 556ms
Take Memory: 3300KB
Submit time: 2017-01-14 11:21:54
****************************************************/