主页 / 问题 / 767979
Accepted
elena
Asked:2020-01-08 20:39:30 +0000 UTC2020-01-08 20:39:30 +0000 UTC

如何对从 1 到 n 的整数进行排序，以便从第二个开始的每个数字完全除以它左侧的数字之和

  • 772

数组总是以 1 开始并以某事结束，n并且数字按顺序排列

例如，如果有一个数组[1,2,3,4,5] ，输出应该是[3,1,4,2,5]

PS 有时间限制——1秒，数组最大长度可达10000个数字（所有数字按顺序排列，不重复）

以下是目前发布的内容：

def check(a): #проверка подходит массив под условие или нет
    E = a[0]
    out = False
    for i in a[1:]:
        if(E%i==0):
            out = True
        if(E%i!=0):
            return False
        E=E+i
    return out


def sort(arr): #сортировка, тут у нас простой перебор комбинаций 
    n = len(arr) 
    for a in range(n):
        for b in range(n):
            if(b==a): continue 
            E = arr[b] #сумма чисел стоящих левее
            for c in range(n):
                if(c==b): continue
                if(E%arr[c]!=0): #если сумма чисел стоящих левее делится на текущее нацело то меняем текущее и предыдущее числа местами
                    temp = arr[c-1]
                    arr[c-1] = arr[c]
                    arr[c] = temp
                if(check(arr)): return arr #если массив проходим проверку возвращаем его

                E=E+arr[c]
python

4 个回答

  1. Best Answer

    最终答案。在 C++ 中，是的:)

    #include <iostream>
#include <iomanip>

using namespace std;


int main()
{
    int N;
    cin >> N;
    int m = N/2;
    for(int i = 1; i <= m; ++i)
        cout << (m+i) << " " << i << " ";

    if (N % 2) cout << (2*m+1);

    cout << endl;
}

    所以，如果是N = 2m，那么我们写下数字

    m+1, 1, m+2, 2, ..., 2m, m

    如果N = 2m+1，那么

    m+1, 1, m+2, 2, ..., 2m, m, 2m+1

    一切。

    我不会删除中间答案，但带有返回的搜索示例有时很好。以及关于解决方案存在的信息如何也可以清除大脑:)

    请注意——您可以亲眼看到条件“最多 10000，1 秒”会自动导致完全不同的参数 :)永远不要懒惰地列出完整的条件！

    • 12

  2. @Harry 算法在 Python 中的实现：

    def div_sort(array):
    m = N // 2
    result = []
    for i in range(0, m):
        result.append(array[m+i])
        result.append(array[i])
    if N % 2:
        result.append(array[N-1])
    return result


N = int(input('N = '))
print(div_sort(range(1, N+1)))

    如果不是置换原始数组的元素，而是动态生成结果，那么我们可以稍微简化代码：

    def div_sort(N):
    m = N // 2
    result = []
    for i in range(1, m+1):
        result.append(m+i)
        result.append(i)
    if N % 2:
        result.append(N)
    return result


N = int(input('N = '))
print(div_sort(N))
    • 6

  3. 作为一个中间答案 - 显然有一些我还不知道的确切算法 - 有一个返回的迭代方法。完整的枚举将在后十个完全关闭......

    我们只是对选项进行排序 - 依次替换第一个数字，作为第二个 - 只有满足条件的那些，然后是这两个的第三个 - 所以我们切断了大部分不合适的组合......但它仍然是太长。

    我不知道如何使用 python，这里是在 C++ 中返回的这个迭代：

    #include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <numeric>

using namespace std;

vector<bool> v;

bool test(vector<bool>&b, int n, vector<int>&r)
{
    if (n == b.size())
    {
        for(auto i: r) cout << setw(3) << i; cout << endl;
        return true;
    }
    int sum = accumulate(r.begin(),r.end(),0);
    for(int j =0; j < b.size(); ++j)
    {
        if (b[j] == false)
        {
            if (sum % (j+1) != 0) continue;
            b[j] = true;
            r.push_back(j+1);
            bool res = test(b,n+1,r);
            r.pop_back();
            b[j] = false;
            if (res) return true;
        }
    }
    return false;
}


int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i) v.push_back(false);

    vector<int> r;
    test(v,0,r);

}

    这是 35 的有效示例。如您所见，对于 10000，它不是一个选项...

    您可以通过以相反的顺序获取数字来加快速度 - 但仍然不是很多：

    https://ideone.com/1c9Z5T

    • 4

  4. 最简单的选择是编写一个函数来检查数组是否按“应有的方式”排序，并将该数组的所有可能排列提供给它（顺便说一下，它们可以使用库函数获得）。这将是所谓的。“搜索算法”。

    顺便说一句，可能没有合适的排列；不可能“按原样”对这个特定数组进行排序。（这在正常排序中不会发生=）

    当你有“一些”正确的（检查这个）算法来解决你手中的问题时，考虑它是否需要在操作数量方面进行优化是有意义的。也许不吧 ;）

    • 1

相关问题