ИНФОРМАТИКА ДВУМЕРНЫЕ МАССИВЫ. ЗАДАНИЕ НА 25 БАЛЛОВ. КТО ПРАВИЛЬНО РЕШИТ- ПОСТАВЛЮ ЛУЧШИЙ ОТВЕТ.
Напишите программу, которая определяет, сколько раз встречается в матрице элемент, равный K .
Входные данные
В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 ≤ N , M ≤ 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В следующей строке записано целое число K .
Выходные данные
Программа должна вывести количество элементов матрицы, равных K .
сериг задачи в фотке
Подсчитайте, сколько раз элемент встречается в последовательности, используя рекурсивный Python
Я пытаюсь подсчитать, сколько раз элемент встречается в последовательности, будь то список чисел или строка, он отлично работает для чисел, но я получаю сообщение об ошибке при попытке найти букву типа «i» в строка :
Ошибка типа: неподдерживаемые типы операндов для +: ‘int’ и ‘NoneType’
5 ответов
Проблема в том, что вы первый if , который явно проверяет, является ли ввод пустым списком:
Если вы хотите, чтобы он работал с str и list , вы должны просто использовать:
Короче говоря, любая пустая последовательность считается ложной в соответствии с тестированием значения истинности в Python и любая непустая последовательность считается верной. Если вы хотите узнать больше об этом, я добавил ссылку на соответствующую документацию.
Вы также можете опустить цикл while здесь, потому что он не нужен, потому что он всегда будет возвращаться в первой итерации и, следовательно, выходить из цикла.
Итак, результат будет примерно таким:
В случае, если вы не только заинтересованы в том, чтобы заставить его работать, но и хотите сделать его лучше, есть несколько возможностей.
Логический подкласс из целых чисел
В Python логические значения являются просто целыми числами, поэтому они ведут себя как целые числа, когда вы выполняете арифметику:
Таким образом, вы можете легко вставить if else :
Потому что f == s[0] возвращает True (который ведет себя как 1), если они равны, или False (ведет себя как 0), если они не равны. Скобки не нужны, но я добавил их для ясности. А поскольку базовый случай всегда возвращает целое число, сама функция всегда будет возвращать целое число.
Избегание копий в рекурсивном подходе
Ваш подход создаст много копий ввода из-за:
Это создает поверхностную копию всего списка (или строки, . ) за исключением первого элемента. Это означает, что у вас на самом деле есть операция, которая использует O(n) (где n — количество элементов) время и память при каждом вызове функции, и поскольку вы делаете это рекурсивно, сложность времени и памяти будет <
Вы можете избежать этих копий, например, передав индекс:
Поскольку мне нужно было передать текущий индекс, я добавил еще одну функцию, которая принимает индекс (я предполагаю, что вы, вероятно, не хотите, чтобы индекс передавался в вашей публичной функции), но если вы хотите, вы можете сделать его необязательным аргументом:
Однако есть, вероятно, еще лучший способ. Вы можете преобразовать последовательность в итератор и использовать ее внутренне, в начале функции вы извлекаете следующий элемент из итератора и, если элемента нет, вы завершаете рекурсию, в противном случае вы сравниваете элемент и затем возвращаетесь в оставшийся итератор. :
Конечно, вы также можете использовать внутренний метод, если хотите избежать затрат на iter вызов, которые необходимы только при первом вызове функции. Однако это микрооптимизация, которая может не привести к заметно более быстрому выполнению:
Преимущество обоих этих подходов состоит в том, что они не используют (много) дополнительной памяти и могут избежать копий. Так что должно быть быстрее и занимать меньше памяти.
Однако для длинных последовательностей у вас возникнут проблемы из-за рекурсии. Python имеет рекурсивный лимит (который настраивается, но только в некоторой степени):
Рекурсия с использованием разделяй и властвуй
Есть способы смягчить (вы не можете решить проблему глубины рекурсии, если вы используете рекурсию) эту проблему. Подход, который регулярно используется — разделяй и властвуй. По сути, это означает, что вы делите любую имеющуюся последовательность на 2 (иногда больше) части и вызываете функцию для каждой из этих частей. Подоконник рекурсии заканчивается, когда остается только один элемент:
Глубина рекурсии теперь изменена с n на log(n) , что позволяет сделать вызов, который ранее не удался:
Однако, поскольку я использовал нарезку, это снова создаст много копий. Использование итераторов будет сложным (или невозможным), потому что итераторы не имеют размера (как правило), но легко использовать индексы:
Использование встроенных методов с рекурсией
Может показаться глупым использовать встроенные методы (или функции) в этом случае, потому что уже есть встроенный метод для решения проблемы без рекурсии, но здесь он есть, и он использует метод index , который и строки, и списки имеют:
Использование итерации вместо рекурсии
Рекурсия действительно мощная, но в Python вы должны бороться с лимитом рекурсии и потому, что нет хвостового вызова Оптимизация в Python часто довольно медленная. Это можно решить с помощью итераций вместо рекурсии:
Итерационные подходы с использованием встроенных модулей
Если вам удобнее, вы можете также использовать выражение генератора вместе с <
Опять же, это основывается на том факте, что логические значения ведут себя как целые числа, и поэтому sum добавляет все вхождения (единицы) со всеми не вхождениями (нулями) и, таким образом, дает общее количество подсчетов.
Но если кто-то уже использует встроенные модули, было бы стыдно не упомянуть встроенный метод (который есть и в строках, и в списках): count :
В этот момент вам, вероятно, больше не нужно оборачивать его внутри функции, и вы можете просто использовать только метод напрямую.
Если вы даже хотите пойти дальше и сосчитать все элементы, вы можете использовать Counter в модуле встроенных коллекций:
Производительность
Я часто упоминал копии и их влияние на память и производительность, и я действительно хотел представить некоторые количественные результаты, чтобы показать, что это действительно имеет значение.
Я использовал мой веселый проект simple_benchmarks здесь (это сторонний пакет, поэтому, если вы хотите запустить его, вы должны установить его):
Это log-log, масштабируемый для значительного отображения диапазона значений, а меньшее — быстрее.
Можно ясно видеть, что оригинальный подход становится очень медленным для длинных входных данных (потому что он копирует список, который он выполняет в O(n**2) ), в то время как другие подходы ведут себя линейно. То, что может показаться странным, это то, что подходы «разделяй и властвуй» работают медленнее, но это потому, что для этого требуется больше вызовов функций (а вызовы функций в Python стоят дорого). Однако они могут обрабатывать гораздо более длинные входные данные, чем варианты итератора и индекса, прежде чем достигнут предела рекурсии.
Было бы легко изменить подход «разделяй и властвуй», чтобы он работал быстрее, на ум приходит несколько возможностей:
- Переключитесь на «не разделяй и властвуй», когда последовательность короткая.
- Всегда обрабатывайте один элемент за вызов функции и делите только остальную часть последовательности.
Но, учитывая, что это, вероятно, просто упражнение по рекурсии, которое выходит за рамки.
Однако все они работают намного хуже, чем при использовании итеративных подходов:
Особенно с помощью метода count списков (но также и строк) и ручной итерации намного быстрее.
Ошибка в том, что иногда у вас просто нет возвращаемого значения. Поэтому возврат 0 в конце вашей функции исправляет эту ошибку. Есть много лучших способов сделать это в Python, но я думаю, что это просто для обучения рекурсивному программированию.
Существует гораздо более идиоматический способ сделать это, чем использовать рекурсию: используйте встроенный метод count для подсчета вхождений.
Однако, если вы хотите сделать это с помощью итерации , вы можете применить аналогичный принцип. Преобразуйте его в список, затем выполните итерацию по списку.
Вы делаете вещи трудным путем, по моему мнению.
Вы можете использовать Counter из коллекций, чтобы сделать то же самое.
Counter вернет объект dict, который содержит количество всего в вашем объекте. Выполнение .get (f) для объекта dict вернет счетчик для определенного элемента, который вы ищете. Это работает со списками чисел или строкой.
Если вы обязаны и решили сделать это с помощью рекурсии, я настоятельно рекомендую по возможности вдвое сократить проблему, а не сокращать ее один за другим. Половина позволяет вам иметь дело с гораздо более крупными случаями, не сталкиваясь с переполнением стека.
Примеры решения задач на строки символов. Часть 1
В данной теме приведены примеры решения некоторых распространенных задач на строки символов без использования стандартных функций языка Python.
Перед изучением темы рекомендуется ознакомиться с темами:
Содержание
- 1. Рекурсивная функция CountCharacterToString() . Определение количества вхождений заданного символа в строке
- 2. Функция IsCharDigit() . Определить, есть ли цифрой символ, заданный номером позиции в строке
- 2.1. Способ 1. Непосредственное определение принадлежности символа диапазону цифр
- 2.2. Способ 2. Использование функции ord()
- 2.3. Способ 3. Использование стандартной функции isdigit()
- 2.4. Способ 4. Использование строки сравнения
- 4.1. Использование стандартной функции count()
- 4.2. Решение без использования функции count()
Search other websites:
1. Рекурсивная функция CountCharacterToString() . Определение количества вхождений заданного символа в строке
в котором осуществляется определение принадлежности отдельного символа s[index] диапазону чисел от ‘0’ до ‘9’ .
Результат выполнения программы
2.2. Способ 2. Использование функции ord()
В этом способе можно использовать функцию ord() , которая возвращает код символа. Символ ‘0’ имеет код 48, символ ‘1’ имеет код 49 и т.д. Соответственно, символ, соответствующий последней цифре, имеет код 57.
Поэтому, в вышеприведенном примере (способ 1) фрагмент строки
можно заменить следующим фрагментом строки
2.3. Способ 3. Использование стандартной функции isdigit()
Функция isdigit() из библиотеки Python позволяет определить, является ли символ цифрой. С учетом этого, модифицированный вариант функции IsCharDigit() имеет вид
2.4. Способ 4. Использование строки сравнения
Этот способ хорошо подходит для определения принадлежности символа некоторому множеству символов, содержащему все возможные значения. Символы, образующие множество символов для сравнения, формируются в виде строки. В нашем случае сравниваются символы цифр, поэтому строка сравнения имеет вид:
Вышеприведенная строка содержит все множество цифр числа. В соответствии с вышесказанным, измененная функция IsCharDigit() выглядит следующим образом.
3. Функция IsCharOp() . Определить количество символов +, –, *, /, % в строке
Функция IsCharOp() получает параметром строку и определяет количество символов операций (+, –, *, /, %) в этой строке. Чтобы уменьшить количество сравнений, в функции используется дополнительная строка
Напишите программу, которая определяет, сколько раз встречается в матрице элемент, равный k .
входные данные
в первой строке записаны через пробел размеры матрицы: количество строк n и количество столбцов m ( 1 ≤ n , m ≤ 100 ). в следующих n строках записаны строки матрицы, в каждой – по m натуральных чисел, разделённых пробелами. в следующей строке записано целое число k .выходные данные
программа должна вывести количество элементов матрицы, равных k
входные данные
4 5
1 2 3 4 5
6 12 8 9 10
11 12 12 14 15
16 17 18 12 20
12
выходные данные
4
c++