Страницы

Поиск по вопросам

вторник, 26 ноября 2019 г.

Как отсортировать целые числа от 1 до n так, чтобы каждое число, начиная со второго, делило сумму чисел, стоящих левее него, нацело


Массив всегда начинается с 1 и заканчивается каким-нибудь n и числа идут по порядку

Наример, есть массив [1,2,3,4,5]
на выходе должно получится [3,1,4,2,5]

P.S. Имеется ограничение по времени - 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]

    


Ответы

Ответ 1



Окончательный ответ. На С++, правда :) #include #include 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 секунда" автомато наводит на совсем другие рассуждения :) Никогда не ленитесь выкладывать полное условие!

Ответ 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))

Ответ 3



Как промежуточный ответ - явно есть какой-то точный алгоритм, который мне пока н известен - есть метод перебора с возвратом. Полный перебор заткнется уже на втором десятке окончательно... Мы просто перебираем варианты - подставляя поочередно первое число, в качестве второг - только те, которые удовлетворяют условию, потом третьи для этих двух - так мы отсечем львиную долю негодных комбинаций... но все равно это будет слишком долго. На python'е не умею, вот этот перебор с возвратом на C++: #include #include #include #include #include using namespace std; vector v; bool test(vector&b, int n, vector&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 r; test(v,0,r); } Тут действующий пример для 35. Как видите, для 10000 не вариант... Можно ускорить, беря числа в обратном порядке - но все равно ненамного: https://ideone.com/1c9Z5T

Ответ 4



Саааамый простой вариант — написать функцию, которая проверяет, является ли масси отсортированным «как надо», и подать ей на вход все возможные перестановки этого массива (а их можно получить с помощью библиотечных функций, кстати). Это будет т.н. «переборный алгоритм». Между прочим, не исключено, что подходящих перестановок и не будет, т.е. данный конкретный массив отсортировать «как надо» невозможно. (В обычной сортировке такого не бывает =) Когда у вас в руках будет «какой-нибудь» корректный (проверьте это) алгоритм решени задачи, имеет смысл подумать, а нужно ли его оптимизировать по числу операций. Может быть и нет ;)

Комментариев нет:

Отправить комментарий