Python

Перевести с языка си на питон.

В файле text.txt записана последовательность чисел. Возможно ли убрать из последовательности один элемент так, чтобы последовательность стала строго возрастающей?
Вот что у меня получилось на си:
int main(void)
{
FILE* in;
int k,n;
int* A;
k=0;
in=fopen("text.txt","r");
if (in==NULL)
return 1;
fscanf(in,"%d",&n);
A=(int*)malloc(n*sizeof(int));
for (i=0;i<n;i++)
fscanf(in,"%d",&A[i]);
for (i=1;iA[i-1])
k++;
if (k==(n-1))
printf("Убирать нет смысла");
else
if (k==(n-2))
printf("Можно");
else
printf("Нельзя");
return 1;
}
Помогите, пожалуйста, перевести это на питон.
Aren Kuchuryan
Aren Kuchuryan
15
L = None
with open("text.txt", "r") as f:
L = list(map(int, f.read().split()))

i = 0
while i < len(L):
LL = L[:i]+L[i+1:]
if sorted(LL) == LL:
print("Можно")
break
i+=1

if i == len(L) : print("Нельзя")
Леонид С
Леонид С
72 294
Лучший ответ
Aren Kuchuryan Большое спасибо! Я так понимаю, что решение задачи отличается от моего?
Aren Kuchuryan А не подскажете, для чего нужен split? И что означает эта строка: LL = L[:i]+L[i+1:]?
Кичайкин Алексей Честно говоря, так себе.
Решение с асимптотикой O(n^2 * log(n)), когда можно спокойно написать линейное.
Aren Kuchuryan А можете вкратце рассказать, что означает строка: LL = L[:i]+L[i+1:]?
Aren Kuchuryan k=0
if ((len(L)==1) or (len(L)==2) or (len(L)==None) ): //Проверка длины массива
print("Задача не имеет смысла")
for i in range(1, len(L)): //Проверка на возрастание всего массива
if L[i]>L[i-1]:
k+=1
if k==(len(L)-1):
print("Задача не имеет смысла")

Решил немного добавить несколько проверок в программу. Проблема в том, что после "print("Задача не имеет смысла")" нужно выйти из программы, но как это сделать? Тут нельзя же написать return 1, как в си.
Aren Kuchuryan 1) А можно ли так сделать проверку на неудачное открытие файла:
if f==None:
----------print("Can't open the file")
----------sys.exit(0)
2)Можно ли так закрыть файл в этой программе:
f.close()
Aren Kuchuryan Хотя здесь, наверное, придется переделать начало программы, чтобы сделать проверку на неуспешное открытие файла
Вот я попытался свой вариант, чтобы побыстрее было.
В правильности не уверен, но вроде бы работает.
Предполагается, что в файле записано по одному числу в строке.

A = [0,0,0]
n_down = 0
with open("text.txt", "r") as f:
~~~~for i in range(3):
~~~~~~~~try:#try-на случай если в файле меньше трех чисел
~~~~~~~~~~~~A[i] = int(f.readline())
~~~~~~~~except:
~~~~~~~~~~~~A[i] = A[i-1]+1
~~~~n_down += A[0]>=A[2]
~~~~for a in f:
~~~~~~~~try:#try - на случай если есть строк - не числа, например пустые строки
~~~~~~~~~~~~A[0],A[1],A[2] = A[1],A[2], int(a)
~~~~~~~~~~~~n_down += A[0]>=A[2]
~~~~~~~~except:
~~~~~~~~~~~~pass
~~~~n_down += A[1]>=A[2]

if n_down > 1:
~~~~print("Нельзя")
else:
~~~~print("Можно")
Максим Марченко
Максим Марченко
21 729
Кичайкин Алексей Контртест:
1 9 1
Можно использовать метод динамического программирования.

Асимптотика: O(n).

Спокойно можно сократить динамику до чисто одномерной, но так интуитивно понятнее.
dp[i][j] означает, является ли префикс массива длины i - 1 возрастающей последовательностью, если мы удалим или не удалим последний элемент (j может быть либо 1, либо 0).

База: очевидно, что при длинах 1 и 2 ответ всегда "да".
Переход: если мы удалим последний элемент нашего префикса, то нам хватит рассмотреть всего лишь префикс на 1 элемент короче без удаленных элементов (это вообще одно и то же). В противном случае мы возьмем максимум из двух величин, которые можно посмотреть в коде:
1) мы могли либо удалить предпоследний элемент, тогда мы сравниваем последний и пред-предпоследний
2) а могли не удалять, тогда сравним последний и предпоследний.

<...>
dp = [[0] * 2 for _ in range(n)]
dp[0], dp[1] = [True, True], [True, True]
for i in range(2, n):
~~~~dp[i][0] = max(dp[i - 1][0] and a[i] > a[i - 1], dp[i - 1][1] and a[i] > a[i - 2])
~~~~dp[i][1] = dp[i - 1][0]
print("yes" if (dp[-1][0] or dp[-1][1]) else "no")
Eugeniu Birita
Eugeniu Birita
8 645

Похожие вопросы