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