PAT乙级 1005.继续(3n+1)猜想

236

和1001一样,不过这题体现出了STL的优越性

题目


原题链接

每个测试用例的输出占一行,按从大到小的顺序输出关键数字。数字间用1个空格隔开,但一行中最后一个数字后没有空格。

输入格式:每个测试输入包含1个测试用例,第1行给出一个正整数K(<100),第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值,数字间用空格隔开。

输出格式:每个测试用例的输出占一行,按从大到小的顺序输出关键数字。数字间用1个空格隔开,但一行中最后一个数字后没有空格。

输入样例
6
3 5 6 7 8 11


输出样例
7 6


解析


模拟跑一边1001的函数,每次都判断下中间值是不是输入列表里有的值,有的话说明这个数不是关键数,没有被标记过的就是答案

代码


C++解法


#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 105;

bool isKeyNum[maxn];
vector<int> vec;

void Callatz(int n) {
    bool isFirst = true;
    while (n > 1) {
        if (isFirst) {
            isFirst = false;
        } else {
            auto iter = lower_bound(vec.begin(), vec.end(), n);
            if (*iter == n) {
                int idx = distance(vec.begin(), iter);
                isKeyNum[idx] = false;
            }
        }
        if (n % 2) {
            n = (n * 3 + 1) / 2;
        } else {
            n /= 2;
        }
    }
}

int main() {
    // cin.tie(false);
    cin.sync_with_stdio(false);

    int n;
    cin >> n;

    vec.clear();
    memset(isKeyNum, true, sizeof(isKeyNum));

    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        vec.insert(lower_bound(vec.begin(), vec.end(), a), a);
    }

    for (int i : vec)
        Callatz(i);

    bool isFirst = true;
    for (int i = n - 1; i >= 0; --i)
        if (isKeyNum[i]) {
            if (isFirst)
                isFirst = false;
            else
                cout << " ";
            cout << vec[i];
        }
    cout << endl;

    return 0;
}


Python解法


def Callatz(n):
    global keyNum
    isFirst = True
    while n > 1:
        if isFirst:
            isFirst = False
        else:
            if n in keyNum:
                keyNum.remove(n)
        if n % 2 == 1:
            n = (3 * n + 1) / 2
        else:
            n /= 2


n = int(input())
lst = [int(i) for i in input().split(' ')]
lst.sort(reverse=True)
keyNum = lst.copy()
for i in range(n):
    Callatz(lst[i])
print(" ".join([str(i) for i in keyNum]))


Java解法


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


class Main {
    public static Scanner in;
    public static ArrayList<Integer> lst;
    public static ArrayList<Boolean> isKeyNum;

    public static void Callatz(int n) {
        boolean isFirst = true;
        while (n > 1) {
            if (isFirst) {
                isFirst = false;
            } else {
                int idx = lst.indexOf(n);
                if (idx != -1) {
                    isKeyNum.set(idx, false);
                }
            }
            if (n % 2 == 1)
                n = (3 * n + 1) / 2;
            else
                n /= 2;
        }
    }

    public static void main(String args[]) {
        in = new Scanner(System.in);
        int n = in.nextInt();
        lst = new ArrayList<Integer>();
        isKeyNum = new ArrayList<Boolean>();

        for (int i = 0; i < n; ++i) {
            int a = in.nextInt();
            lst.add(Integer.valueOf(a));
            isKeyNum.add(true);
        }
        Collections.sort(lst);
        for (int i : lst) {
            Callatz(i);
        }
        boolean isFirst = true;
        for (int i = n - 1; i >= 0; --i) {
            if (isKeyNum.get(i)) {
                if (isFirst)
                    isFirst = false;
                else
                    System.out.print(' ');
                System.out.print(lst.get(i));
            }
        }
        System.out.print('\n');
        in.close();
    }
}
发布评论
  • 点击查看/关闭被识别为广告的评论