Как найти числа фибоначчи в массиве - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given an array arr[] of size N, the task is to find the composite Fibonacci numbers present in the given array.

Examples:

Input: arr[] = {13, 55, 7, 3, 5, 21, 233, 144, 6}
Output: 55 21 144
Explanation:
Composite array elements are {55, 21, 144, 6}.
Fibonacci array elements are {55, 21, 144}.
Therefore, array elements which are both composite as well as Fibonacci are {55, 21, 144}.

Input: arr[] = {34, 13, 11, 8, 3, 55, 233}
Output: 3
Explanation:
Composite array elements are {34, 8, 55}
Fibonacci array elements are {34, 8, 55}
Therefore, array elements which are both composite as well as Fibonacci are {34, 8, 55}.

Approach: Follow the steps below to solve the problem:

Initialize a variable, say Max to store the largest element of the array.
Create a Set to store all Fibonacci numbers up to Max.
Initialize an array, say sieve[], to store all the prime numbers using Sieve Of Eratosthenes.
Finally, traverse the array and check if the current array element is both composite and Fibonacci number or not. If found to be true, then print the current element.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

set<int> createhashmap(int Max)

{

set<int> hashmap;

int curr = 1;

int prev = 0;

hashmap.insert(prev);

while (curr <= Max) {

hashmap.insert(curr);

int temp = curr;

curr = curr + prev;

prev = temp;

}

return hashmap;

}

vector<bool> SieveOfEratosthenes(

int Max)

{

vector<bool> isPrime(Max, true);

isPrime[0] = false;

isPrime[1] = false;

for (int p = 2; p * p <= Max; p++) {

if (isPrime[p]) {

for (int i = p * p; i <= Max;

i += p) {

isPrime[i] = false;

}

return isPrime;

}

int cntFibonacciPrime(int arr[], int N)

{

int Max = arr[0];

for (int i = 1; i < N; i++) {

Max = max(Max, arr[i]);

}

vector<bool> isPrime

= SieveOfEratosthenes(Max);

set<int> hashmap

= createhashmap(Max);

for (int i = 0; i < N; i++) {

if (arr[i] == 1)

continue;

if ((hashmap.count(arr[i]))

&& !isPrime[arr[i]]) {

cout << arr[i] << " ";

}

int main()

{

int arr[] = { 13, 55, 7, 3, 5, 21,

233, 144, 89 };

int N = sizeof(arr) / sizeof(arr[0]);

cntFibonacciPrime(arr, N);

return 0;

}

Java

import java.util.*;

class GFG{

static boolean[] isPrime;

static HashSet<Integer>

createhashmap(int Max)

{

HashSet<Integer> hashmap =

new HashSet<>();

int curr = 1;

int prev = 0;

hashmap.add(prev);

while (curr < Max)

{

hashmap.add(curr);

int temp = curr;

curr = curr + prev;

prev = temp;

}

return hashmap;

}

static void SieveOfEratosthenes(int Max)

{

isPrime = new boolean[Max];

Arrays.fill(isPrime, true);

isPrime[0] = false;

isPrime[1] = false;

for (int p = 2;

p * p <= Max; p++)

{

if (isPrime[p])

{

for (int i = p * p; i <= Max;

i += p)

{

isPrime[i] = false;

}

static void cntFibonacciPrime(int arr[],

int N)

{

int Max = arr[0];

for (int i = 1; i < N; i++)

{

Max = Math.max(Max, arr[i]);

}

SieveOfEratosthenes(Max);

HashSet<Integer> hashmap =

createhashmap(Max);

for (int i = 0; i < N; i++)

{

if (arr[i] == 1)

continue;

if ((hashmap.contains(arr[i])) &&

!isPrime[arr[i]])

{

System.out.print(arr[i] + " ");

}

public static void main(String[] args)

{

int arr[] = {13, 55, 7, 3, 5,

21, 233, 144, 89};

int N = arr.length;

cntFibonacciPrime(arr, N);

}

Python3

import math

def createhashmap(Max):

hashmap = {""}

curr = 1

prev = 0

hashmap.add(prev)

while (curr <= Max):

hashmap.add(curr)

temp = curr

curr = curr + prev

prev = temp

return hashmap

def SieveOfEratosthenes(Max):

isPrime = [1 for x in range(Max + 1)]

isPrime[0] = 0

isPrime[1] = 0

for p in range(0, int(math.sqrt(Max))):

if (isPrime[p]):

for i in range(2 * p, Max, p):

isPrime[i] = 0

return isPrime

def cntFibonacciPrime(arr, N):

Max = arr[0]

for i in range(0, N):

Max = max(Max, arr[i])

isPrime = SieveOfEratosthenes(Max)

hashmap = createhashmap(Max)

for i in range(0, N):

if arr[i] == 1:

continue

if ((arr[i] in hashmap) and

(not(isPrime[arr[i]]))):

print(arr[i], end = " ")

arr = [ 13, 55, 7, 3, 5,

21, 233, 144, 89 ]

N = len(arr)

cntFibonacciPrime(arr, N)

C#

using System;

using System.Collections.Generic;

class GFG{

static bool[] isPrime;

static HashSet<int> createhashmap(int Max)

{

HashSet<int> hashmap = new HashSet<int>();

int curr = 1;

int prev = 0;

hashmap.Add(prev);

while (curr < Max)

{

hashmap.Add(curr);

int temp = curr;

curr = curr + prev;

prev = temp;

}

return hashmap;

}

static void SieveOfEratosthenes(int Max)

{

isPrime = new bool[Max];

for(int i = 0;i<Max;i++)

isPrime[i] = true;

isPrime[0] = false;

isPrime[1] = false;

for(int p = 2; p * p <= Max; p++)

{

if (isPrime[p])

{

for(int i = p * p; i <= Max;

i += p)

{

isPrime[i] = false;

}

static void cntFibonacciPrime(int []arr,

int N)

{

int Max = arr[0];

for(int i = 1; i < N; i++)

{

Max = Math.Max(Max, arr[i]);

}

SieveOfEratosthenes(Max);

HashSet<int> hashmap = createhashmap(Max);

for(int i = 0; i < N; i++)

{

if (arr[i] == 1)

continue;

if ((hashmap.Contains(arr[i])) &&

!isPrime[arr[i]])

{

Console.Write(arr[i] + " ");

}

public static void Main(String[] args)

{

int []arr = { 13, 55, 7, 3, 5,

21, 233, 144, 89 };

int N = arr.Length;

cntFibonacciPrime(arr, N);

}

Javascript

<script>

function createhashmap(Max)

{

var hashmap = new Set();

var curr = 1;

var prev = 0;

hashmap.add(prev);

while (curr <= Max)

{

hashmap.add(curr);

var temp = curr;

curr = curr + prev;

prev = temp;

}

return hashmap;

}

function SieveOfEratosthenes(Max)

{

var isPrime = Array(Max + 1).fill(true);

isPrime[0] = false;

isPrime[1] = false;

for(var p = 2; p * p <= Max; p++)

{

if (isPrime[p])

{

for(var i = p * p; i <= Max;

i += p)

{

isPrime[i] = false;

}

return isPrime;

}

function cntFibonacciPrime(arr, N)

{

var Max = arr[0];

for(var i = 1; i < N; i++)

{

Max = Math.max(Max, arr[i]);

}

var isPrime = SieveOfEratosthenes(Max);

var hashmap = createhashmap(Max);

for(var i = 0; i < N; i++)

{

if (arr[i] == 1)

continue;

if (hashmap.has(arr[i]) &&

!isPrime[arr[i]])

{

document.write( arr[i] + " ");

}

var arr = [ 13, 55, 7, 3, 5, 21,

233, 144, 89 ];

var N = arr.length;

cntFibonacciPrime(arr, N);

</script>

Time Complexity: O(N + Max * log(log(Max))), where Max is the largest element in the array
Auxiliary Space: O(N)

Last Updated :
09 Jun, 2021

Like Article

Save Article

Источник

Определение чисел Фибоначчи

Числа Фибоначчи это последовательность натуральных чисел, которая начинается с чисел ноль и один, а каждое следующее число равно сумме двух предыдущих:

Первые 10 чисел Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Получение первых `n` чисел Фибоначчи

Чтобы найти первые n чисел Фибоначчи, можно создать массив размера n, первые два элемента будут равны нулю и единице, а остальные элементы можно получить, используя цикл и вышеприведённую формулу:

int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; ++i) {
    f[i] = f[i - 1] + f[i - 2];
}

В коде предполагается существование переменной n, которую можно ввести с клавиатуры, например так:

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

После заполнения массива f полученные первые n чисел Фибоначчи можно вывести на экран с помощью цикла:

for (int i = 0; i < n; ++i) {
    System.out.println(f[i]);
}

Онлайн пример кода

Стоит заметить, что тип int в Java позволяет хранить только числа до 2³¹-1, поэтому вышеприведённым способом получится вычислить только первые 46 чисел Фибоначчи (при попытке вычислить сорок седьмое число Фибоначчи произойдёт переполнение и получится отрицательное число). Используя тип данных long вместо int без переполнения получится вычислить первые 91 число Фибоначчи. Чтобы вычислять последующие числа Фибоначчи можно воспользоваться классом BigInteger, который реализует длинную арифметику в Java.

Получения `n`-ого по счёту числа Фибоначчи

Для получения только n-ого числа Фибоначчи не обязательно использовать массив, достаточно завести две переменных a и b, в которых будут храниться последние два числа Фибоначчи, и пересчитывать эти переменные n - 2 раза:

int a = 0;
int b = 1;
for (int i = 2; i <= n; ++i) {
    int next = a + b;
    a = b;
    b = next;
}
System.out.println(b);

Онлайн пример кода

Рекурсивное вычисление чисел Фибоначчи

Существует также рекурсивный способ вычисления чисел Фибоначчи. Однако его не рекомендуется использовать, потому что, в отличии от предыдущих двух способов, которые работают за линейное время от n, рекурсивный способ может работать значительно дольше.

// функция, возвращающая n-ое число Фибоначчи
public static int f(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return f(n - 1) + f(n - 2);
    }
}

Онлайн пример кода

Рекурсивный способ работает за экспоненциальное время от n, например для n равного 46 рекурсивный способ работает дольше пяти секунд, а способ с запоминанием последних двух чисел Фибоначчи работает менее одной десятой секунды).

Рекурсивный способ может работать долго, потому что в процессе вычисления функция будет много раз вызываться от одного и того же аргумента (например, при вычислении f(5) функция сделает рекурсивные вызовы к f(4) и f(3), оба рекурсивных вызова обратятся к f(2)), что приведёт к многократному повторению одних и тех же операций.

Быстрое вычисление чисел Фибоначчи с помощью быстрого умножения матриц (используя `O(log n)` операций умножения)

Рассмотрим матрицу:

Используя матричное умножение, рекуррентное соотношение для последних двух чисел Фибоначчи может быть записано так:

Расписывая это соотношение, получаем:

Таким образом, чтобы найти n-ое число Фибоначчи достаточно возвести матрицу A в степень n - 1. Это можно сделать алгоритмом быстрого возведения в степень.

// матричное умножение двух матриц размера 2 на 2
public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
    // [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
    // [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
    return new BigInteger[][]{
            {a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])), a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
            {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])), a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))},
    };
}

// возведение матрицы размера 2 на 2 в степень n
public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
    if (n == 0) {
        // любая матрица в нулевой степени равна единичной матрице
        return new BigInteger[][]{
                {BigInteger.ONE, BigInteger.ZERO},
                {BigInteger.ZERO, BigInteger.ONE}
        };
    } else if (n % 2 == 0) {
        // a ^ (2k) = (a ^ 2) ^ k
        return matrixPowerFast(matrixMultiplication(a, a), n / 2);
    } else {
        // a ^ (2k + 1) = (a) * (a ^ 2k)
        return matrixMultiplication(matrixPowerFast(a, n - 1), a);
    }
}

// функция, возвращающая n-ое число Фибоначчи
public static BigInteger fibonacci(int n) {
    if (n == 0) {
        return BigInteger.ZERO;
    }

    BigInteger[][] a = {
            {BigInteger.ONE, BigInteger.ONE},
            {BigInteger.ONE, BigInteger.ZERO}
    };
    BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
    // nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
    BigInteger nthFibonacci = powerOfA[0][0];
    return nthFibonacci;
}

public static void main(String[] args) {
    System.out.println(fibonacci(1024));
}

Онлайн пример кода

Источник

B правой части каждого сообщения есть стрелки ⇧ и ⇩. Не стесняйтесь оценивать ответы. Чтобы автору вопроса закрыть свой тикет, надо выбрать лучший ответ. Просто нажмите значок ✔ в правой части сообщения.

Guest

Переменной T присвоить значение true, если среди элементов массива х есть хотя бы одно число Фибоначчи, и значение false иначе
Pascal

Код:

uses crt;

function fib(k:byte):real;
begin
if (k=1) then begin fib:=0;exit;end;
if (k=2) then begin fib:=1;exit;end;

fib:=fib(k-1)+fib(k-2);
end;


const n=10;

var x:array[1..n] of integer;
i,k:byte;
t:boolean;
begin
clrscr;
writeln('введите ',n,' элементов массива');
for i:=1 to n do
read(x[i]);
readln;
t:=false;
for i:=1 to n do
if x[i]=fib(k) then
begin
t:=true;

end;
writeln(t);
readln
end.

помогите, разлобраться. Вот что есть уже.

nayke

во первых советую числа фибоначи определить в массиве вначале а не определять число рекусивно для каждого x.
например

Код:

fib: array[1..20] of integer;
fib[1]:=1;
fib[2]:=2;
for i:=3 to 20 do
fib[i]:=fib[i-1]+fib[i-2];

ну а сравнить есть ли число в массиве можно как

Код:

for i:=1 to n do
begin
for j:=1 to 20 do
if x[i]=fib[j] then begin t:=true;break;end;
if t then break;
end;

так как последовательность фибоначи будет отсортирована то можно всячески оптимизировать алгоритм, например используя дихотомический поиск, но для лабы с маленькими значениями и так пойдет.

Источник

На занятии объясняется, как работать с одномерными массивами в Паскале, как использовать генератор случайных чисел — функцию random в Паскале. Рассматривается пример того, как вывести числа Фибоначчи

Материалы сайта labs-org.ru направлены на практическое освоение языка программирования Pascal. Краткие теоретические сведения не претендуют на полное освещение материала по теме; необходимую информацию можно найти в сети Интернет в большом количестве. В наши же задачи входит предоставление возможности получения практических навыков программирования на Паскале. Решенные наглядные примеры и задания изложены по мере увеличения их сложности, что позволит с легкостью изучить материал с нуля.

Содержание:

Одномерные массивы в Паскале
- Объявление массива
- Инициализация массива
- Вывод элементов массива
- Динамические массивы (pascalAbc.Net)
- Функция Random в Pascal
- Числа Фибоначчи в Паскале
- Максимальный (минимальный) элемент массива
- Поиск в массиве
- Циклический сдвиг
- Перестановка элементов в массиве
- Выбор элементов и сохранение в другой массив
- Сортировка элементов массива

Одномерные массивы в Паскале

Объявление массива

Массивы в Паскале используются двух типов: одномерные и двумерные.
Определение одномерного массива в Паскале звучит так: одномерный массив — это определенное количество элементов, относящихся к одному и тому же типу данных, которые имеют одно имя, и каждый элемент имеет свой индекс — порядковый номер.
Описание массива в Паскале (объявление) и обращение к его элементам происходит следующим образом:

Объявление массива

var dlina: array [1..3] of integer;
begin
dlina[1]:=500; 
dlina[2]:=400; 
dlina[3]:=150;
...

dlina — идентификатор (имя) массива;

для объявления используется служебное слово Array (в переводе с англ. «массив» или «набор»);

[1..3] — в квадратных скобках ставится номер (индекс) первого элемента, затем две точки и индекс последнего элемента массива, т.е. по сути, указывается количество элементов; количество элементов массива называется размерностью массива

of integer (с англ. «из целых чисел») — указывает, к какому типу относится массив, of здесь — служебное слово.

Объявить размер можно через константу:

Инициализация массива

Кроме того, массив может быть сам константным, т.е. все его элементы в программе заранее определены. Описание такого массива выглядит следующим образом:

const a:array[1..4] of integer = (1, 3, 2, 5);

Заполнение последовательными числами:

Результат:
A[1] = 8, A[2] = 9, A[3] = 10, ..., A[N] = A[N-1] + 1

Ввод с клавиатуры:

Пример: Рассмотрим, как происходит ввод массива в Паскале:

writeln ('введите кол-во элементов: ');
readln(n); {если кол-во заранее не известно, - запрашиваем его}
for i := 1 to n do begin
   write('a[', i, ']=');
   read(a[i]);
   ...
end;
...

✍ Пример результата:

введите кол-во элементов: 
3
a[1]=5
a[2]=7
a[3]=4

Вывод элементов массива

Пример: Рассмотрим, как вывести массив в Паскале:

var
  a: array[1..5] of integer; {массив из пяти элементов}
  i: integer;
begin
a[1]:=2;
a[2]:=4;
a[3]:=8;
a[4]:=6;
a[5]:=3;
writeln('Массив A:');
for i := 1 to 5 do
    write(a[i]:2); {вывод элементов массива}
end.

✍ Пример результата:

Для работы с массивами чаще всего используется в Паскале цикл for с параметром, так как обычно известно, сколько элементов в массиве, и можно использовать счетчик цикла в качестве индексов элементов.

Задача Array 0. Необходимо задать вещественный массив размерностью 6 (т.е. из шести элементов); заполнить массив вводимыми значениями и вывести элементы на экран. Использовать два цикла: первый — для ввода элементов, второй — для вывода.

Пример результата:

введите элемент массива: 3.0
введите элемент массива: 0.8
введите элемент массива: 0.56
введите элемент массива: 4.3
введите элемент массива: 23.8
введите элемент массива: 0.7
Массив =  3, 0.8, 0.56, 4.3, 23.8, 0.7

[Название файла: taskArray0.pas]

В данном примере работы с одномерным массивом есть явное неудобство: присваивание значений элементам.

Обработка массивов в Паскале, так же как и заполнение массива, происходит обычно с использованием цикла for.

Динамические массивы (pascalAbc.Net)

Основным недостатком статических массивов является то, что их размер нельзя задать с учетом текущих обрабатываемых данных. Приходится описывать массивы с максимально возможным значением количества элементов, выделяя для них столько памяти, сколько может потребоваться для хранения самой большого из возможных наборов исходных данных.

Основной особенностью динамических массивов является возможность выделения для них памяти на любом этапе выполнения программы.

Имеется возможность корректировки размера динамического массива как в сторону его уменьшения, так и в сторону увеличения.

Объявление:

var a: array of integer;
var n:=readInteger;
a:=new integer[n]; // инициализация, выделение памяти для элементов массива

или:

var a: array of integer;
var n:=readInteger;
SetLength(a,n); // устанавливаем размер

Аналогичным образом массивы могут описываться в качестве параметров подпрограмм, например:

procedure p(a: array of integer);

Созданные элементы сразу получают начальное значение, равное нулевому значению соответствующего типа: для чисел это целый или вещественный нуль, для символов — символ с кодом 0, для строк и других ссылочных типов данных — нулевая ссылка nil

Объявление и инициализация массива:

Пример:

begin
  var a: array of integer;
  a := new integer[3];
  a[0] := 5;
  a[1] := 2;
  a[2] := 3;
end.

или в одну строку:

begin
  var a: array of integer;
  a := new integer[3](5,2,3);
  print(a)
end.

или короткая запись:

var a:=Arr(1,2,3);// по правой части - integer

Элементы динамического массива всегда индексируются от 0.

Ввод элементов:

Пример:

var a:=ReadArrInteger(5); // ввод пяти целых
var a:=ReadArrReal(5); // ввод пяти вещественных

Функции генерации массивов:

1. ArrFill :

var a := ArrFill(10, 1); // массив из 10 целых чисел, равных 1

2. ArrGen :

var a := ArrGen(ReadInteger, 1, e -> e + 2); // массив, состоящий из n первых положительных нечетных чисел
a.Print;

Проход по элементам массива:

Пример:

for var i:=0 to a.Length-1 do
  a[i] += 1;

или:

for var i := 0 to a.High do
  a[i] += 1;

Проход по элементам (только для чтения):
Пример:

foreach var x in a do
  Print(x)

Размер динамического массива (т. е. количество его элементов) можно определить с помощью его свойства Length

Для динамического массива определены еще два свойства: Low и High, определяющие соответственно нижнюю и верхнюю границу диапазона изменения индекса. Свойство a.Low всегда возвращает 0, а свойство a.High определяется как a.High = a.Length – 1

Простой вывод элементов:

Writeln(a); // пример вывода: [1,5,3,13,20]

или метод массива Print:

a.Print; // пример вывода: 1 5 3 13 20
a.PrintLines; // каждый элемент с новой строки

Функция Random в Pascal

Для того чтобы постоянно не запрашивать значения элементов массива используется генератор случайных чисел в Паскаль, который реализуется функцией Random. На самом деле генерируются псевдослучайные числа, но суть не в этом.

Для генерации чисел от 0 до n (не включая само значение n, целые числа в интервале [0,N)) используется запись random (n).
Перед использованием функции необходимо инициализировать датчик случайных чисел с помощью процедуры randomize.

Диапазон в Паскале тех самых случайных чисел от a до b задается формулой:

Пример: Заполнение массива случайными числами в Pascal:

var f: array[1..10] of integer;
    i:integer;
begin
randomize;
for i:=1 to 10 do
  begin
   f[i]:=random(10); { интервал [0,9] }   
   write(f[i],' ');
  end;
end.

✍ Пример результата:

Для вещественных чисел в интервале [0,1):

var x: real;
...
x := random(0.0,1.0);;         { интервал [0,1), т.е. единица не включена }

PascalABC.NET:

Сгенерированный случайным образом кортеж из двух (Random2), либо из трех (Random3) элементов:

var (a, b, c) := Random3(10.0, 20.0); // диапазон [10, 20)
write(a:0:2,' ',b:0:2,' ', c:0:2) // 14.73 18.63 19.72

Массив из 10 сгенерированных случайным образом целых чисел в диапазоне [0;99]:

Пример:

var a:=arrRandomInteger(10);

или с дополнительными параметрами (диапазон [5;15]):

var a:=arrRandomInteger(10,5,15);

Задача Array 1. Необходимо задать массив размерностью 5, заполнить массив случайными числами в интервале [-1,1] и вывести элементы на экран: определить три позиции для вывода каждого элемента, с двумя знаками после запятой.

Пример результата:

Массив =  0.22 0.00 -0.69 -0.35 -0.11

[Название файла: taskArray1.pas]

Числа Фибоначчи в Паскале

Наиболее распространенным примером работы с массивом является вывод ряда чисел Фибоначчи в Паскаль. Рассмотрим его.

Пример: Ряд чисел Фибоначчи: 1 1 2 3 5 8 13…

f[0]:=1;   
f[1]:=1; 
f[2]:=2;  
…
или
f[2]:=f[0]+f[1];
f[3]:=f[1]+f[2];
или

Получили формулу элементов ряда.

Пример: Вычислить и распечатать первые 20 чисел Фибоначчи.

var i:integer;
f:array[0..19]of integer;
begin
f[0]:=1;
f[1]:=1;
for i:=2 to 19 do
begin
  f[i]:=f[i-1]+f[i-2];
  writeln(f[i])
end;
end.

На данном примере, становится понятен принцип работы с числовыми рядами. Обычно, для вывода числового ряда находится формула определения каждого элемента данного ряда. Так, в случае с числами Фибоначчи, эта формула-правило выглядит как f[i]:=f[i-1]+f[i-2]. Поэтому ее необходимо использовать в цикле for при формировании элементов массива.

Задача Array 2. Дан ряд из 10 произвольных чисел: a[1], a[2], ... , a[10] (использовать функцию random()). Подсчитать и напечатать суммы троек стоящих рядом чисел: a[1]+a[2]+a[3], a[2]+a[3]+a[4], a[3]+a[4]+a[5], …… , a[8]+a[9]+a[10]

Пример результата:

Массив =  2 0 4 29 3 11 26 11 9 4 
mas[1] + mas[2] + mas[3] = 6
mas[2] + mas[3] + mas[4] = 33
mas[3] + mas[4] + mas[5] = 36
mas[4] + mas[5] + mas[6] = 43
mas[5] + mas[6] + mas[7] = 40
mas[6] + mas[7] + mas[8] = 48
mas[7] + mas[8] + mas[9] = 46
mas[8] + mas[9] + mas[10] = 24

[Название файла: taskArray2.pas]

Задача Array 3. Написать программу решения задачи о печати ряда чисел 2 4 8 16 32 ... 512; для заполнения массива использовать цикл Repeat
[Название файла: taskArray3.pas]

Максимальный (минимальный) элемент массива

Псевдокод:

Поиск максимального элемента по его индексу:

PascalABC.NET:

Минимальный элемент и его индекс:

Решение 1:

  // …
  var (min, minind) := (a[0], 0);  
  for var i:=1 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

Решение 2:

  // …
  var (min, minind) := (real.MaxValue, 0);  
  for var i:=0 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

Решение 3:

begin
  var a := new integer[5];
  a := arrRandomInteger(5); // [86,37,41,45,76] 
  print(a.Min,a.IndexMin); // 37  1
end.

Задача Array_min: Найдите минимальный элемент массива. Выведите элемент и его индекс.

Пример результата:

9 5 4 22 23 7 3 16 16 8 
Минимальный элемент массива A[7]=3

[Название файла: taskArray_min.pas]

Задача Array 4. Дан массив из 10 целочисленных элементов. Найти количество отрицательных и вывести количество на экран.

Пример результата:

3 4 6 -1 6 -2 1 5 0 1 
Количество отрицательных элементов: 2

[Название файла: taskArray4.pas]

Задача Array 5. Найти минимальное и максимальное из n введенных чисел (массива). Определить расстояние между этими элементами.

3  2  6  1  3  4  7  2  >>>  min=1, max=7, distance=3

[Название файла: taskArray5.pas]

Задача Array 6. Дан целочисленный массив размера N. Вывести все содержащиеся в данном массиве четные числа в порядке убывания их индексов, а также их количество K.

N=4
mas: 8 9 2 5
>>> 2 8 количество= 2

[Название файла: taskArray6.pas]

Задача Array 7. Ввести с клавиатуры массив из 5 элементов, найти в нем два максимальных элемента и их номера.

Пример:

Исходный массив:
4   -5   10  -10  5
максимальные A[3]=10, A[5]=5

[Название файла: taskArray7.pas]

Поиск в массиве

Рассмотрим сложный пример работы с одномерными массивами:

Пример: Дан массив из 10 чисел. Определить, есть ли в массиве число, введенное пользователем. Если есть – выводить «найдено», если нет – «не найдено».
Сложность задания заключается в том, что выводить слова «найдено» или «не найдено» необходимо один раз.

Для решения поставленной задачи понадобится оператор break — выход из цикла.
Решение Вариант 1. Цикл for:

PascalABC.NET:

Cтандартные методы a.IndexOf(x) и a.LastIndexOf(x):

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.IndexOf(3)) // 1
end.

или метод a.Contains(x) наравне с x in a:

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.Contains(3)); // True
  print(3 in a)// True
end.

Рассмотрим эффективное решение:

Задача: найти в массиве элемент, равный X, или установить, что его нет.

Алгоритм:

начать с 1-го элемента (i:=1);
если очередной элемент (A[i]) равен X, то закончить поиск иначе перейти к следующему элементу.

решение на Паскале Вариант 2. Цикл While:

Поиск элемента в массиве

Предлагаем посмотреть подробный видео разбор поиска элемента в массиве (эффективный алгоритм):

Задача Array 8. Заполнить массив из 10 элементов случайными числами в интервале [0..4] и вывести номера всех элементов, равных X.

Пример:

	 Исходный массив:
	 4  0  1  2  0  1  3  4  1  0
	 Что ищем? 0
	 A[2], A[5], A[10]

[Название файла: taskArray8.pas]

Циклический сдвиг

Пример: сдвинуть элементы массива влево на 1 позицию, первый элемент становится на место последнего.

Решение:

Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];

Программа:

PascalABC.NET:

Циклический сдвиг влево:

  // …
  var v := a[0];
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := v;

Циклический сдвиг вправо:

  // …
  var v := a[a.Length-1];
  for var i:=a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := v;

Задача Array 9. Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг влево без первого элемента.
Пример:

Исходный массив:
  4  -5   3  10  -4  -6   8 -10  1  0
Результат:
  4   3  10  -4  -6   8 -10   1  0 -5

[Название файла: taskArray9.pas]

Перестановка элементов в массиве

Рассмотрим, как происходит перестановка или реверс массива.

Пример: переставить элементы массива в обратном порядке

Решение:

Алгоритм:

Псевдокод:

Программа:

PascalABC.NET:

Перестановка (ревёрс):

Решение 1:

begin
var a: array of integer := (1,3,5,7); 
var n := a.Length;
for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
End.

Решение 2 (стандартная процедура Reverse()):

begin
var a:=new integer[10];
a:=arrRandomInteger(10);
print(a);// [41,81,84,63,12,26,88,25,36,72] 
Reverse(a);
print(a) //[72,36,25,88,26,12,63,84,81,41] 
end.

Задача Array 10. Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и сделать реверс всех элементов, кроме последнего.
Пример:

 Исходный массив:
-5  3   10  -4  -6   8 -10  1   0  4
 Результат:
0  1  -10   8  -6  -4  10  3  -5  4

[Название файла: taskArray10.pas]

Выбор элементов и сохранение в другой массив

Пример: найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив

Решение:

Решение: подсчитывать количество найденных элементов с помощью счетчика count, очередной элемент устанавливать на место B[count]. Переменой count необходимо присвоить 1.

Вывод массива B:

writeln('Выбранные элементы');
for i:=1 to count-1 do
   write(B[i], ' ')

PascalABC.NET:

Процедура SetLength():

// ...
for var i := 0 to a.length - 1 do 
    if a[i] < 0 then
    begin
      b[j] := a[i];
      j += 1;
    end;
  SetLength(b, j);

Задача Array 11. Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0.
Пример:

	 Исходный массив:
	 40   57   30  71  84
	 Заканчиваются на 0:
	 40 30

[Название файла: taskArray11.pas]

Сортировка элементов массива

Сортировка методом «Пузырька»

В таком типе сортировок массив представляется в виде воды, маленькие элементы — пузырьки в воде, которые всплывают наверх (самые легкие).
При первой итерации цикла элементы массива попарно сравниваются между собой:предпоследний с последним, пред предпоследний с предпоследним и т.д. Если предшествующий элемент оказывается больше последующего, то производится их обмен.
При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой. Значит, число сравнений будет на одно меньше. То же самое касается каждой последующей итерации.

Pascal

PascalABC.NET

for i:=1 to N-1 do begin
   for j:=N-1 downto i do
     if A[j] > A[j+1] then begin
       с := A[j];
       A[j] := A[j+1];
       A[j+1] := с;
     end;
 end;

for var i := 0 to arr.High - 1 do
    for var j := arr.High - 1 downto i do
      if arr[j] > arr[j + 1] then 
        Swap(arr[j], arr[j + 1]);

Задача Array 12. Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину массива по возрастанию, а вторую – по убыванию (методом ‘Пузырька’).

Пример:
Исходный массив:
14  25  13  30  76  58  32  11  41  97
Результат:
13  14  25  30  76  97  58  41  32  11

[Название файла: taskArray12.pas]

Сортировка методом выбора

в массиве ищется минимальный элемент и ставится на первое место (меняется местами с A[1]);
среди оставшихся элементов также производится поиск минимального, который ставится на второе место (меняется местами с A[2]) и т.д.

Pascal

PascalABC.NET

for i := 1 to N-1 do begin
  min:= i ;
  for j:= i+1 to N do
    if A[j] < A[min] then min:=j; 
  if min <> i then begin
    c:=A[i]; 
    A[i]:=A[min]; 
    A[min]:=c;
  end;
end;

for var i := 0 to a.High-1 do
  begin
    var (min,imin) := (a[i],i);
    for var j := i + 1 to a.High do
      if a[j] < min then
        (min,imin) := (a[j],j);
    Swap(a[imin],a[i]);
  end;

Задача Array 13: Заполнить массив из 10 элементов случайными числами в интервале [0..50] и отсортировать его по возрастанию суммы цифр

Пример:
Исходный массив:
14  25  13  12  76  58  21  87  10  98
Результат:
10  21  12  13  14  25  76  58  87  98

[Название файла: taskArray13.pas]

PascalABC.NET:

Стандартная процедура sort():

Sort(a);
SortByDescending(a);

Быстрая сортировка или quick sort

Алгоритм:

Выбирается и запоминается средний элемент массива (присвоим X):

Инициализируем две переменные (будущие индексы массива): L:=1, R:=N (N — количество элементов).
Увеличиваем L и ищем первый элемент A[L], который больше либо равен X (в итоге он должен находиться справа).
Уменьшаем R и ищем элемент A[R], который меньше либо равен X (в итоге он должен находиться слева).
Смотрим, если L<=R, то меняем местами A[L] и A[R], возвращаемся к пункту 3.

Выполнение на Паскале:

procedure QSort ( first, last: integer);
var L, R, c, X: integer;
begin
  if first < last then begin
    X:= A[(first + last) div 2];
    L:= first; R:= last;
 while L <= R do begin
   while A[L] < X do L:= L + 1;
   while A[R] > X do R:= R - 1;
   if L <= R then begin
     c:= A[L]; A[L]:= A[R]; A[R]:= c;
     L:= L + 1; R:= R - 1;
   end;
 end;
  QSort(first, R);   QSort(L, last);
  end;
end.

Задача Array 14:
Заполнить массив из 10 элементов случайными числами в интервале [-50..50] и отсортировать его с помощью алгоритма быстрой сортировки.

[Название файла: taskArray14.pas]

Источник

C++

Java

Python3

C#

Javascript

Определение чисел Фибоначчи

Получение первых n чисел Фибоначчи

Получения n-ого по счёту числа Фибоначчи

Рекурсивное вычисление чисел Фибоначчи

Быстрое вычисление чисел Фибоначчи с помощью быстрого умножения матриц (используя O(log n) операций умножения)

Guest

nayke

Одномерные массивы в Паскале

Объявление массива

Инициализация массива

Вывод элементов массива

Динамические массивы (pascalAbc.Net)

Функция Random в Pascal

Числа Фибоначчи в Паскале

Максимальный (минимальный) элемент массива

Поиск в массиве

Циклический сдвиг

Перестановка элементов в массиве

Выбор элементов и сохранение в другой массив

Сортировка элементов массива

Получение первых `n` чисел Фибоначчи

Получения `n`-ого по счёту числа Фибоначчи

Быстрое вычисление чисел Фибоначчи с помощью быстрого умножения матриц (используя `O(log n)` операций умножения)