3n+1数列问题

简介: 3n+1数列问题

3n+1数列问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

SubmitStatistic

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;
}


相关文章
|
6月前
27.数列1,2,2,3,3,3,4,4,4,4,5,……
27.数列1,2,2,3,3,3,4,4,4,4,5,……
50 0
|
算法
斐波那切数列
斐波那切数列
138 0
7-8 菲波那契数列
7-8 菲波那契数列
63 0
利用递归求斐波纳契数列的和
递归的方法更加简单,更容易理解
LeetCode 665.非递减数列
LeetCode 665.非递减数列
100 0
LeetCode 665.非递减数列
|
开发者 Python
求斐波那契数列数列 | 学习笔记
快速学习 求斐波那契数列数列
102 0
求斐波那契数列数列 | 学习笔记