3n+1数列问题 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss 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> typedef struct no { int data; struct no *next; }node; node *create(int m,int n) { node *p,*head; head = (node *)malloc(sizeof(node)); head->next=NULL; for(int i=0;i<n;i++) { if(m%2==0) { p=(node *)malloc(sizeof(node)); m/=2; p->data = m; p->next=head->next; head->next=p; } else { m=m*3+1; node *q; if(head->next) q=head->next; else q=head; while(q->next) { q=q->next; } p=(node *)malloc(sizeof(node)); p->data=m; p->next=NULL; q->next=p; q=p; } } return head; } void display(node *head) { node *q; q=head->next; while(q) { q->next?printf("%d ",q->data):printf("%d",q->data); q=q->next; } printf("\n"); } int main() { int m=10,n=10; node *head; while(scanf("%d %d",&m,&n)!=EOF) { head = create(m,n); display(head); } }