Lesson #17. Sequence

Дата изменения: 9 февраля 2023

Theory

Standard sequence generators

Range(a,b: integer): sequence of integer

print(Range(1,10)); // [1,2,3,4,5,6,7,8,9,10]

Range(a,b,step: integer): sequence of integer

print(Range(1,10,2)); // [1,3,5,7,9]

Range(c1,c2: char): sequence of char

print(Range('a','k')); // [a,b,c,d,e,f,g,h,i,j,k]

Partition(a,b: real; n: integer): sequence of real

print(Partition(0.0, 6.0, 4)); // divide into 4 equal parts [0, 1.5, 3, 4.5, 6]

SeqRandomInteger(n: integer[; a,b: integer]): sequence of integer;

var q:=SeqRandomInteger(5,10,20); print(q); // [12,18,16,14,16]

SeqRandomReal(n: integer[; a,b: real]): sequence of real;

var q:=SeqRandomReal(3, 1.0, 5.0); print(q); // [4.98996168374548,2.22339218166815,2.81110574389394]

Seq(params a: array of T): sequence of T;

foreach var x in Seq (1,3,8) do print(x*x); // 1 9 64

SeqFill(count: integer; x: T): sequence of T;

begin var q:=SeqFill(7,5); print(q); // [5,5,5,5,5,5,5] end.
{0.1 points} Task 1:

To do: Create sequence of integers from -20 to 30 with a step of 3 (Range function).

Expected output:

[-20,-17,-14,-11,-8,-5,-2,1,4,7,10,13,16,19,22,25,28]


[Program name: 17task-01.pas]

{0.1 points} Task 2:

To do: Create N random numbers of a sequence from -50 to 100 (SeqRandom function).

Expected output:

enter n
>>15
[-23,13,-27,2,46,-26,10,92,60,-9,75,28,85,7,18]


[Program name: 17task-02.pas]

Sequence generators with lambda-expressions

The following functions are used to generate sequences using lambda expressions:

• SeqGen(count: integer; f: integer -> T): sequence of T;
• begin var sq:=SeqGen(5,x->x+1); sq.println; // 1 2 3 4 5 end.
• SeqGen(count: integer; first: T; next: T -> T): sequence of T;
• begin var sq:=SeqGen(5, 4, x->x+1); sq.println; // 4 5 6 7 8 end.
• SeqGen(count: integer; first,second: T; next: (T,T) -> T): sequence of T;
• begin var sq:=SeqGen(5, 1,3, (x,y)->x+y); sq.println; // 1 3 4 7 11 end.
Lab: Create a sequence of N Fibonacci elements

Algorithm:

var n:=readInteger; var sq3:=SeqGen(n,1,1,(x,y)->x+y); sq3.println();
• SeqWhile(first: T; next: T -> T; pred: T -> boolean): sequence of T;

begin var sq:=seqWhile(2,x->x*2,x->x<=1024); sq.println; // 2 4 8 16 32 64 128 256 512 1024 end.
• SeqWhile(first,second: T; next: (T,T) -> T; pred: T -> boolean): sequence of T;
• SeqGen(count: integer; f: integer -> T): sequence of T;
{0.1 points} Task 3:

To do: Using lambda expression, create a sequence of N even numbers starting at 10 (SeqGen should be used)

Expected output:

Enter n
>> 7
10 12 14 16 18 20 22


[Program name: 17task-03.pas]

{0.1 points} Task 4:

To do: Create the following sequence: 1 3 9 27 81 243 729 2187 6561 19683 (SeqGen should be used)

Expected output:

1 3 9 27 81 243 729 2187 6561 19683


[Program name: 17task-04.pas]

{0.1 points} Task 5:

To do: Create a sequence of 15 numbers: 2 1 0.5 0.25 0.125 0.0625 0.03125 0.015625 ... (specifying the first element and the function to get the next one) (SeqGen should be used)

Expected output:

2  1  0.5  0.25  0.125  0.0625  0.03125  0.015625 0.0078125 0.00390625
0.001953125 0.0009765625 0.00048828125 0.000244140625 0.0001220703125


[Program name: 17task-05.pas]

{0.1 points} Task 6:

To do: Create the following sequence: 2017 2012 2007 2002 1997 1992 1987 1982 1977 1972 (SeqGen should be used)

Expected output:

2017 2012 2007 2002 1997 1992 1987 1982 1977 1972


[Program name: 17task-06.pas]

Lab:

To do: Create a sequence of N numbers generated by the iterative process: а1=2, аk=(аk-1+1)*аk-1, k = 2,3,… (SeqGen should be used)

Expected output:

Enter n 7
2 6 42 1806 3263442 -1461943274 -757910022


✍ Algorithm:

begin var n:=readInteger('Enter n'); var sq:=SeqGen(n,2,x->(x+1)*x); sq.println(); end.
{0.2 points} Task 7:

To do: Create a sequence of N numbers generated by the iterative process: a1 = 5, ak = ak-1 / 2-1, k = 2,3, … (SeqGen should be used)

Expected output:

Enter n
>> 9
5  1.5  -0.25  -1.125  -1.5625 -1.78125 -1.890625 -1.9453125 -1.97265625


[Program name: 17task-7.pas]

{0.2 points} Task 8:

To do: Create a sequence of N numbers generated by the iterative process: а1=1, а2=2, аk=аk-1+2аk-2, k=3,… (SeqGen should be used)

Expected output:

Enter n
>>7
1 2 4 8 16 32 64


[Program name: 17task-8.pas]

{0.2 points} Task 9:

To do: Create a sequence of N numbers generated by the iterative process: а1=1, а2=2, аk=(аk-1+аk-2)/2, k=3,… (SeqGen should be used)

Expected output:

Enter n
>> 7
1 2 1.5 1.75 1.625 1.6875 1.65625


[Program name: 17task-9.pas]

Cutting off a seq

• Take(count)
• begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Take(2); // 1 2 s1.Println; end.
• TakeLast(count)
• Skip(count)
• begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Skip(2); // 3 4 5 6 7 8 9 10 s1.Println; end.
begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Skip(3)+s.Take(3); // 4 5 6 7 8 9 10 1 2 3 s1.Println; end.
• SkipLast(count)
• TakeWhile(T -> boolean)
• TakeWhile((T, integer) -> boolean)
• SkipWhile(T -> boolean)
• SkipWhile((T, integer) -> boolean)
• Slice(from,step[,count]: integer): sequence of T;
• Distinct
• Only unique elements:

var a:=Seq(1,3,1,4,1,5); a.Distinct.Print; // 1 3 4 5

Infinite sequence generators

• Cycle()
• Repeating a sequence block

Seq(1,2,10,5).Cycle().Take(15).Println; // 1 2 10 5 1 2 10 5 1 2 10 5 1 2 10

Take  is used to restrict

• Repeat
• Infinite sequence of numbers

var q:=55.Repeat.Take(10).Println; // 55 55 55 55 55 55 55 55 55 55
• Step
• Generating an infinite sequence with a step

var q:=5.Step(2).Take(10).Println; // 5 7 9 11 13 15 17 19 21 23
• Iterate
• Generating an infinite sequence using a lambda-function

var q:=10.Iterate(x->x-2).Take(10).Println; // 10 8 6 4 2 0 -2 -4 -6 -8
• Distinct — only unique elements
• var a:=Seq(1,3,1,4,1,5); a.Distinct.Print; // 1 3 4 5
{0.1 points} Task 10:

To do: Create 3 infinite sequences:
1) the elements equaled 5,
2) the elements equaled numbers 2 5 8 11 …;
3) iterate function with a rule to output 1 2 4 8 16 32 64 128 256 512
4) the elements equaled to repetitions of the numbers 1 2 10 5 (Seq(1,2,10,5).Cycle()).

Output 100 elements of each.

Expected output:

5 5 5 5 ...
2 5 8 11 ...
1 2 4 8 16 32 64 128 256 512 ...
1 2 10 5 1 2 10 5 1 2 10 5 ...


[Program name: 17task-10.pas]

Where method (queries)

• Where(T -> boolean)
• Lab:

To do: Create a query to filter out even elements of the sequence.

The result examples:

Sequence: 1 2 3 4 5 6 7 8 9 10
Result: 2 4 6 8 10


✍ Algorithm:

begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Where(x->x mod 2=0); end.
• Where((T, integer) -> boolean)
• begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Where((x,i)->i mod 2=0); // 1 3 5 7 9 s1.Println; end.

x — an element, and i — an index of the element.

{0.1 points} Task 11:

To do: A sequence of positive and negative integers is given. Create a query to filter out:
1) the positives from that sequence
2) the elements divisible by 5
3) odd elements

Expected output:

sequence:
-4 25 -7 -12 16
result 1:
25 16
result 2:
25
result 3:
25 -7


[Program name: 17task-11.pas]

Select method (queries)

When projection is used each element will be modified (despite when where is used)

• Select(T -> TRes)
• Lab:

To do: Create a query to square each element of the sequence.

The result examples:

Sequence: 1 2 3 4 5 6 7 8 9 10
Result: 1 4 9 16 25 36 49 64 81 100


✍ Algorithm:

begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Select(x->x*x); // 1 4 9 16 25 36 49 64 81 100 s1.Println; end.
{0.1 points} Task 12:

To do: A sequence of integers is given. Create a query to get a sequence in which each element is the square root of the corresponding element of the original sequence.

Expected output:

sequence:
4 25 7 12 16
result:
2 5 2.64575131106459 3.46410161513775 4


[Program name: 17task-12.pas]

Projection and filtering combination:

begin var s:=seqGen(10,x->x+1); // 1 2 3 4 5 6 7 8 9 10 var s1:=s.Where(x -> x mod 2 = 0).Select(x->x*x); // 4 16 36 64 100 s1.Println; end.

Sorting or ordering sequences

• Sorted
• SortedDescending
• OrderBy(T -> TKey)
• var s:=Seq(('Ivanov',20,1),('Petrov',19,2),('Popov',21,1)); s.OrderBy(x->x[0]).Println; // (Ivanov,20,1) (Petrov,19,2) (Popov,21,1) s.OrderBy(x->x[1]).Println; // (Petrov,19,2) (Ivanov,20,1) (Popov,21,1)
• OrderByDescending(T -> TKey)
• To do: This function can be used, for example, to find k maximums in an array:

✍ Algorithm:

begin var a:=Arr(1,3,5,2,7,9,0); var k:=3; a.OrderByDescending(x->x).Distinct.Take(k).Print; // 9 7 5 end.

Scalar Computation

• Count([T -> boolean]): integer
• var a:=Arr(1,2,3,4,5); var b:=a.Count(x->x mod 2 <> 0); // 3 odd elements
NB: In the example Count  is a filter(like Where), which calculates the number of odd elements.
Lab.

To do: Define a sequence using Seq method. Calculate a quantity of x (entered number) within the sequence. You should use count (condition) method.

The result examples:

-1 2 3 -5 2 -7 8 2 11
enter x: 2
there is 2 within the seq 3 times


✍ Algorithm:

begin var c:=Seq(-1,2,3,-5,2,-7,8,2,11); c.Println(); var x:=readinteger('enter x:'); var n:=c.count(c->c=x); println(\$'there is {x} within the seq {n} times '); end.
{0.1 points} Task 13:

To do: Define a sequence using Seq method. Calculate a number of negative elements in a sequence. You should use count (condition) method.

Expected output:

-1 2 3 -5 6 -7 8 9 11
number of negative elements is 3


[Program name: 17task-13.pas]

• Average: double
• Average(T -> числовой_тип): double
• Sum: числовой_тип
• Sum(T -> числовой_тип): числовой_тип
• Lab.

To do: The sequence of 10 integer elements is given. Calculate a sum of the seq elements.

The result examples:

0 1 2 3 4 5 6 7 8 9
sum = 45


✍ Algorithm:

begin var q:=SeqGen(10,x->x).Println; var s:=0.0; foreach var x in q do s+=x; print('sum = ', s) end.

2. LINQ approach:

begin var q:=SeqGen(10,x->x).Println; q.Sum.Print end.
{0.1 points} Task 14:

To do: Calculate a product (multiplication) of 5 sequence elements.

Expected output:

1.2  3.1  6.7  2.8  3.4
product:  237.27648


[Program name: 17task-14.pas]

NB: Average, Sum, Max and Min — are not the filters, they are projections (like Select)
Lab: Calculate the average of Fibonacci elements, which are even and have three-digits

Algorithm:

println(seqWhile(1,1,(x,y)->x+y,x->x div 1000=0) .where (x-> (x>100)and(x<=999)and (x mod 2 =0)).average);
{0.1 points} Task 15:

To do: Find the sum of the first Fibonacci numbers that are one- or two- digits. SeqWhile and sum methods must be used.

Expected output:

sequence: 1 1 2 3 5 8 13 21 34 55 89
sum: 232


[Program name: 17task-15.pas]

Lab:

To do: Calculate the quantity of maximum elements within a sequence.

Expected output:

1 5 2 10 1 10
number of max elements is 2


✍ Algorithm:

begin var c := Seq(1, 5, 2, 10, 1, 10); c.Println(); var k := c.Max(); var res := 0; foreach var i in c do if i = k then res += 1; println('number of max elements is ', res); end.

2. LINQ approach:

begin var c := Seq(1, 5, 2, 10, 1, 10); c.Println(); println('number of max elements is ', c.Count(x->x=c.Max)); end.
{0.2 points} Task 16:

To do: Calculate a sum of odd elements in a sequence.

Expected output:

1 5 2 10 1 10
sum of odd elements  7


[Program name: 17task-16.pas]

{0.2 points} Task 17:
The sequence is given: 1, 4, 5, 2, 7, 10, 1. Print out the elements with even indexes and count their quantity. You have to use where and count  functions with conditions.

Expected output:

1 5 7 1
4


[Program name: 17task-16.pas]

{0.2 points} Task 18:
The seq is given. Find a minimum element of the soubled elements of the seq

Expected output:

6 2 3 4
4


[Program name: 17task-18.pas]

{0.2 points} Task 19:
There is a sequence of reals: 1.2, 3.5, 5.1, 2.2, 7.0, 9.6, 0.7. Output the rounded numbers in the same order (round()), as well as the sum of all rounded numbers. To display the final sequence, use the projection Select, and to calculate the sum — projection Sum must be used,and two variables to store the results.

Expected output:

1 4 5 2 7 10 1
30


[Program name: 17task-19.pas]

Вставить формулу как
Дополнительные настройки
Цвет формулы
Используйте LaTeX для набора формулы
Предпросмотр
$${}$$
Формула не набрана
Вставить