主页 / 问题 / 1540146
Accepted
Nymos
Asked:2023-09-12 00:25:20 +0000 UTC2023-09-12 00:25:20 +0000 UTC

问题的解决方案没有通过测试

  • 772

再次大家晚上好。我正在用Python解决一个问题，遇到了一个问题。我的解决方案没有通过测试。我自己不太明白我的要求是什么，但我认为我们需要强调这个建议Известно, что в языке реальных членов экипажа вероятность появления каждого символа зависит от предыдущего。就我个人而言，有人建议我制作所有符号对的频率字典。现在，当您输入字符时3 aba caba aba daba baa cdaa，它会生成一个数字1，但应该输出一个数字3

这是任务：

亚历山大在太空港的海关工作。有一天，一艘宇宙飞船在完成火星探险后抵达那里。港口的扫描仪已经拉响警报；船上确实有一个火星人，他伪装成船员。不幸的是，扫描仪无法显示谁到底是火星人。

然后亚历山大决定为所有船员申请一个通信协议。 众所周知，在真实船员的语言中， 每个角色出现的概率取决于前一个角色。然而，火星人不知道这一点 ，并试图模仿真正船员的语言，选择 字母而不顾以前的字母。

帮助亚历山大确定哪些船员实际上是火星人。保证这可以用现有的通信协议来完成。

输入格式

第一行包含一个自然数N (3 ≤ N ≤ 10)——船上船员的数量（包括伪装的火星人）。

以下N几行包含相关机组人员的声明文本。每行仅由小拉丁字母和空格组成。所有线的长度总和不超过104。输出格式 打印一个自然数——伪装火星人的陈述文本对应的行号。

输出格式 打印一个自然数——伪装火星人的陈述文本对应的行号。

实施例1

输入数据：

3
aba caba 
aba daba
baa cdaa

输出：

3

这是我使用频率字典执行任务的代码avg_pair_counts：

import numpy as np

N = int(input())

# Чтение высказываний экипажа и создание словарей пар символов
statements = []
pair_dicts = []

for _ in range(N):
    statement = input()
    statements.append(statement)

    pair_dict = {}
    for i in range(len(statement) - 1):
        pair = statement[i:i + 2]
        if pair in pair_dict:
            pair_dict[pair] += 1
        else:
            pair_dict[pair] = 1

    pair_dicts.append(pair_dict)

# Создание словаря всех пар символов
avg_pair_counts = {}
for pair_dict in pair_dicts:
    for pair, count in pair_dict.items():
        if pair in avg_pair_counts:
            avg_pair_counts[pair] += count
        else:
            avg_pair_counts[pair] = count

# Вычисление дисперсии для каждого члена экипажа
min_variance = np.inf
min_index = -1

for i, pair_dict in enumerate(pair_dicts):
    variance = 0
    for pair, count in pair_dict.items():
        diff = count - (avg_pair_counts.get(pair, 0) / N)
        variance += diff ** 2

    if variance < min_variance:
        min_variance = variance
        min_index = i

print(min_index + 1)
python

1 个回答

  1. Best Answer

    这是解决问题中的示例的事情。从字符串中提取字符对。排除带有空格的对。对于其余的对，将计算字符串中的出现次数。字典中仅保留值，这些值被转换为计算变异（方差的平方）的频率。火星人说话的变化很小。

    import collections


def pairs(seq):
    it = iter(seq)
    next(it, None)
    return zip(seq, it)


def frequences(seq):
    counts = collections.Counter(seq).values()
    s = sum(counts)
    return (c / s for c in counts)


def variance(seq):
    c = 0
    s1 = 0
    s2 = 0
    for v in seq:
        c += 1
        s1 += v
        s2 += v * v
    # print((s1 * s1 - s2) / c)
    return (s1 * s1 - s2) / c


def variances(n):
    for _ in range(n):
        yield variance(frequences(p for p in pairs(input()) if ' ' not in p))


print(min((v, i) for i, v in enumerate(variances(int(input())), start=1))[1])

    PS参考示例的变化：

    1    0.21(3)
2    0.21(3)
3    0.18

    PPS变体仅考虑特定人的语音中出现的配对。具有公共频率/出现字典的选项不起作用。

    • 2

相关问题