написал в виде ответа т.к. в каментарий банально не влезет, по сути является вариантом ответа предоставленого: @VladD с той лишь разницей что не прибегает сразу к испльзованию модулей
если позначить 3 первых члена последовательности как x1,x2,x3 получается что каждый элемент последовательности можно описать функцией:
f(j) = a*x1 + b*x2 + c*x3 (1)
где a,b,c определяют количество вхождений элементов: x1,x2,x3
учитывая что нас интересует только последняя позиция в числе можно записать формулу так:
f(x) = a*x1 + b*x2 + c*x3 = a*x1 % 10 + b*x2 % 10 + c*x3 % 10 (2)
где, для каждого из чисел a,b,c справедлива начальная формула: f(k)=f(k-2)+3f(k-3), арифметика по модулю 10 применяется для того чтоб держать множители a,b,c в пределах 10, так как: 10*x % 10 = x
пишем функцию которая в цикле считает числа a,b,c для каждого элемента последовательности, до тех пор пока не найдем период: T (3)
после того как найден период можно получить индекс элемента:
K = (10^10000) % mod T = …
соответственно запускаем функцию (3) еще раз, для числа T: получаем конкретные значения чисел a,b,c. далее используем формулу (1) и получаем результат
p.s. програмка пишется примерно за 30-60 минут
|
elenayagubova 337 / 237 / 103 Регистрация: 26.03.2019 Сообщений: 407 |
||||||||
|
10.02.2020, 14:58 |
8 |
|||||||
|
Решение
1. можно ли обойтись без глобальных переменных и повлияет это както на производительность? Не только можно, но и очень желательно, в первую очередь чтобы избежать возможных ошибок. В данном случае можно адреса max, first, last передавать в качестве параметра в функцию flmax:
2. не совсем понял строку «int max = INT_MIN;» INT_MIN — минимально возможное значение для типа int. Нужно чем-то инициализировать max, чтобы первое число затем записалось в него. Если бы у нас были какие-то ограничения на значения чисел в файле, можно было бы использовать их(например, число строго положительны — можно инициализировать отрицательным числом или нулем). Ваш вариант, при котором в max сразу вычитывается первое число, тоже можно использовать, просто в нем происходит дублирование кода (fscanf()).
3. я не истпользовал EOF. Обязательно ли его писять и для чего он конкретно нужен? я так понял он переводится как «End of file» и обозначает -1. EOF обозначает end of file, все правильно. Если fscanf вернет это значение, значит достигнут конец файла(или произошла какая-то ошибка). Вариант проверки, что fscanf вернул 1 здесь тоже подходит.
Добавлено через 21 минуту
flmax(file, max, first, last); Упс, разумеется, не так, а вот так
1 |
Сообщение было отмечено IvanK1331 как решение
Формулировка задачи:
Нужна помощь в написании программы для создания и обработки массива
вот условие:
Дана последовательность из n вещественных чисел.Найти номер последнего вхождения данного числа в последовательность,или вывести сообщение,что такого числа нет.
Буду очень признателен за помощь!
Код к задаче: «Найти номер последнего вхождения данного числа в последовательность,или вывести сообщение,что такого числа нет»
textual
Листинг программы
const
nmax=100;
var
a: array[1..nmax] of integer;
n,i,x,k: integer;
begin
randomize;
write('Введите размер массива n: ');
readln(n);
write('Введите искомое число x: ');
readln(x);
k:=0;
writeln('Массив:');
for i:=1 to n do
begin
a[i]:=random(9)+1;
write(a[i],' ');
if a[i]=x then k:=i;
end;
writeln;
if k=0 then writeln('Искомого числа в массиве нет') else
writeln('Номер последнего вхождения числа ',x,' = ',k);
readln;
end.
Учитывая отсортированный целочисленный массив, найдите индекс первого или последнего вхождения заданного числа. Если элемент отсутствует в массиве, также сообщите об этом.
Например,
Input:
nums = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]
target = 5
Output:
The first occurrence of element 5 is located at index 1
The last occurrence of element 5 is located at index 3
Input:
nums = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]
target = 4
Output:
Element not found in the array
Потренируйтесь в этой проблеме
Простым решением было бы запустить линейный поиск в массиве и вернуть первое или последнее вхождение данного элемента. Проблема с этим подходом заключается в том, что его временная сложность в наихудшем случае равна O(n), куда n это размер ввода. Это решение также не использует тот факт, что ввод отсортирован. Мы можем легко решить эту проблему в O(log(n)) время, изменив алгоритм бинарного поиска.
Поиск первого вхождения элемента
Стандартный бинарный поиск завершается, как только найдено любое вхождение заданного целевого элемента. Чтобы найти первое вхождение данного элемента, измените двоичный поиск, чтобы он продолжал поиск даже при обнаружении целевого элемента. Вместо этого обновите результат до mid и искать влево (в сторону более низких индексов), т. е. модифицировать наше пространство поиска, регулируя высокое значение до mid-1 при нахождении цели в середине индекса.
Ниже приведена программа на C, Java и Python, которая демонстрирует это:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <stdio.h> // Функция для поиска первого вхождения заданного числа в отсортированном массиве целых чисел int findFirstOccurrence(int nums[], int n, int target) { // область поиска nums[low…high] int low = 0, high = n — 1; // инициализируем результат на -1 int result = —1; // цикл до тех пор, пока пространство поиска не будет исчерпано while (low <= high) { // находим среднее значение в пространстве поиска и сравниваем его с целевым int mid = (low + high)/2; // если цель обнаружена, обновить результат и // поиск влево (нижние индексы) if (target == nums[mid]) { result = mid; high = mid — 1; } // если цель меньше среднего элемента, отбрасываем правую половину else if (target < nums[mid]) { high = mid — 1; } // если цель больше среднего элемента, отбрасываем левую половину else { low = mid + 1; } } // вернуть самый левый индекс или -1, если элемент не найден return result; } int main(void) { int nums[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int n = sizeof(nums)/sizeof(nums[0]); int target = 5; int index = findFirstOccurrence(nums, n, target); if (index != —1) { printf(«The first occurrence of element %d is located at index %d», target, index); } else { printf(«Element not found in the array»); } return 0; } |
Скачать Выполнить код
результат:
The first occurrence of element 5 is located at index 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Main { // Функция для поиска первого вхождения заданного числа // в отсортированном целочисленном массиве public static int findFirstOccurrence(int[] nums, int target) { // область поиска nums[left…right] int left = 0; int right = nums.length — 1; // инициализируем результат на -1 int result = —1; // цикл до тех пор, пока пространство поиска не будет исчерпано while (left <= right) { // находим среднее значение в пространстве поиска и сравниваем его с целевым int mid = (left + right) / 2; // если цель обнаружена, обновить результат и // поиск влево (нижние индексы) if (target == nums[mid]) { result = mid; right = mid — 1; } // если цель меньше среднего элемента, отбрасываем правую половину else if (target < nums[mid]) { right = mid — 1; } // если цель больше среднего элемента, отбрасываем левую половину else { left = mid + 1; } } // вернуть самый левый индекс или -1, если элемент не найден return result; } public static void main(String[] args) { int[] nums = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int target = 5; int index = findFirstOccurrence(nums, target); if (index != —1) { System.out.println(«The first occurrence of element « + target + » is located at index « + index); } else { System.out.println(«Element not found in the array»); } } } |
Скачать Выполнить код
результат:
The first occurrence of element 5 is located at index 1
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Функция поиска первого вхождения заданного числа # в отсортированном списке целых чисел def findFirstOccurrence(nums, target): # пространство поиска nums[left…right] (left, right) = (0, len(nums) — 1) # инициализирует результат значением -1 result = —1 # Цикл # до тех пор, пока пространство поиска не будет исчерпано while left <= right: # находит среднее значение в пространстве поиска и сравнивает его с целевым mid = (left + right) // 2 #, если цель обнаружена, обновить результат и # поиск влево (нижние индексы) if target == nums[mid]: result = mid right = mid — 1 #, если цель меньше среднего элемента, отбросить правую половину elif target < nums[mid]: right = mid — 1 #, если цель больше среднего элемента, отбросить левую половину else: left = mid + 1 # возвращает самый левый индекс или -1, если элемент не найден return result if __name__ == ‘__main__’: nums = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9] target = 5 index = findFirstOccurrence(nums, target) if index != —1: print(f‘The first occurrence of element {target} is located at index {index}’) else: print(‘Element found not in the list’) |
Скачать Выполнить код
результат:
The first occurrence of element 5 is located at index 1
Поиск последнего вхождения элемента
Чтобы найти последнее вхождение элемента, измените стандартный двоичный поиск, чтобы он продолжал поиск даже при обнаружении цели. Вместо этого обновите результат до mid и продолжим поиск вправо (в направлении более высоких индексов), т. е. модифицируем наше пространство поиска, изменив низкие значения на mid+1 при нахождении цели в середине индекса.
Ниже приведена реализация C, Java и Python, основанная на приведенной выше идее:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <stdio.h> // Функция для поиска последнего вхождения заданного числа в отсортированном массиве целых чисел int findLastOccurrence(int nums[], int n, int target) { // область поиска nums[low…high] int low = 0, high = n — 1; // инициализируем результат на -1 int result = —1; // цикл до тех пор, пока пространство поиска не будет исчерпано while (low <= high) { // находим среднее значение в пространстве поиска и сравниваем его с целевым int mid = (low + high)/2; // если цель обнаружена, обновить результат и // поиск вправо (более высокие индексы) if (target == nums[mid]) { result = mid; low = mid + 1; } // если цель меньше среднего элемента, отбрасываем правую половину else if (target < nums[mid]) { high = mid — 1; } // если цель больше среднего элемента, отбрасываем левую половину else { low = mid + 1; } } // вернуть самый левый индекс или -1, если элемент не найден return result; } int main(void) { int nums[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int n = sizeof(nums)/sizeof(nums[0]); int target = 5; int index = findLastOccurrence(nums, n, target); if (index != —1) { printf(«The last occurrence of element %d is located at index %d», target, index); } else { printf(«Element not found in the array»); } return 0; } |
Скачать Выполнить код
результат:
The last occurrence of element 5 is located at index 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Main { // Функция для поиска последнего вхождения заданного числа // в отсортированном целочисленном массиве public static int findLastOccurrence(int[] nums, int target) { // область поиска nums[left…right] int left = 0; int right = nums.length — 1; // инициализируем результат на -1 int result = —1; // цикл до тех пор, пока пространство поиска не будет исчерпано while (left <= right) { // находим среднее значение в пространстве поиска и сравниваем его с целевым int mid = (left + right) / 2; // если цель обнаружена, обновить результат и // поиск вправо (более высокие индексы) if (target == nums[mid]) { result = mid; left = mid + 1; } // если цель меньше среднего элемента, отбрасываем правую половину else if (target < nums[mid]) { right = mid — 1; } // если цель больше среднего элемента, отбрасываем левую половину else { left = mid + 1; } } // вернуть самый левый индекс или -1, если элемент не найден return result; } public static void main(String[] args) { int[] nums = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int target = 5; int index = findLastOccurrence(nums, target); if (index != —1) { System.out.println(«The last occurrence of element « + target + » is located at index « + index); } else { System.out.println(«Element not found in the array»); } } } |
Скачать Выполнить код
результат:
The last occurrence of element 5 is located at index 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# Функция поиска последнего вхождения заданного числа в отсортированном списке целых чисел def findLastOccurrence(nums, target): # пространство поиска nums[left…right] (left, right) = (0, len(nums) — 1) # инициализирует результат значением -1 result = —1 # Цикл # до тех пор, пока пространство поиска не будет исчерпано while left <= right: # находит среднее значение в пространстве поиска и сравнивает его с целевым mid = (left + right) // 2 #, если цель обнаружена, обновить результат и # поиск вправо (более высокие индексы) if target == nums[mid]: result = mid left = mid + 1 #, если цель меньше среднего элемента, отбросить правую половину elif target < nums[mid]: right = mid — 1 #, если цель больше среднего элемента, отбросить левую половину else: left = mid + 1 # возвращает самый левый индекс или -1, если элемент не найден return result if __name__ == ‘__main__’: nums = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9] target = 5 index = findLastOccurrence(nums, target) if index != —1: print(f‘The last occurrence of element {target} is located at index {index}’) else: print(‘Element found not in the list’) |
Скачать Выполнить код
результат:
The last occurrence of element 5 is located at index 3
Временная сложность приведенных выше решений равна O(log(n)) и не требует дополнительного места.
Упражнение:
1. Напишите рекурсивную версию приведенных выше решений.
2. Проверьте, встречается ли данное целое число больше, чем n/2 раз в отсортированном массиве.
Использованная литература:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int max = -1, count = 0, index = -1;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
if (num > max) {
max = num;
count = 1;
index = i;
}
else if (num == max) {
count++;
index = i;
}
}
cout << index << endl;
return 0;
}
Если что я могу и вашу задачу решить, я все-таки нейросеть онлайн, форма
наверху
02:04 05.04.2023
Символы : 548