menu
person

Задача №2891

Дан мас­сив, со­дер­жа­щий не­от­ри­ца­тель­ные целые числа, не пре­вы

Поиск задачи:

Дан мас­сив, со­дер­жа­щий не­от­ри­ца­тель­ные целые числа, не пре­вы­ша­ю­щие 10 000. Не­об­хо­ди­мо вы­ве­сти:

- ми­ни­маль­ный чётный эле­мент, если ко­ли­че­ство чётных эле­мен­тов не боль­ше, чем нечётных;

- ми­ни­маль­ный нечётный эле­мент, если ко­ли­че­ство нечётных эле­мен­тов мень­ше, чем чётных.

На­при­мер, для мас­си­ва из шести эле­мен­тов, рав­ных со­от­вет­ствен­но 4, 6, 12, 17, 9, 8, от­ве­том будет 9 — наи­мень­шее нечётное число, по­сколь­ку нечётных чисел в этом мас­си­ве мень­ше.

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

 

 

 

 

Бей­сик Пас­каль
CONST N=2000
 DIM A(N) AS INTEGER
 DIM I, J, K, M AS INTEGER
 FOR I = 1 TO N
 INPUT A(I)
 NEXT I
 …
 END
const
 N=2000;
 var
 a: array [1..N] of integer;
 i, j, k, m: integer;
 begin
 for i:=1 to N do
 readln(a[i]);
 …
 end.
Си Ал­го­рит­ми­че­ский язык
#include 
#define N 2000
int main(){
int a[N];
int i, j, k, m;
for (i=0; iscanf("%d", &a[i]);
…
return 0;
}
алг
нач
цел N=2000 | Из­ме­нять зна­че­ние
этой пе­ре­мен­ной нель­зя
цел­таб a[1:N]
цел i, j, k, m
нц для i от 1 до N
ввод a[i]
кц
…
кон
Python

// до­пус­ка­ет­ся также ис­поль­зо­вать

// це­ло­чис­лен­ные пе­ре­мен­ные j, k, m

a = []

N = 2000 // ме­нять зна­че­ние N нель­зя

for i in range(0, n):

a.append(int(input()))

 

 

В ка­че­стве от­ве­та Вам не­об­хо­ди­мо при­ве­сти фраг­мент про­грам­мы, ко­то­рый дол­жен на­хо­дить­ся на месте мно­го­то­чия. Вы мо­же­те за­пи­сать ре­ше­ние также на дру­гом языке про­грам­ми­ро­ва­ния (ука­жи­те на­зва­ние и ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Free Pascal 2.6). В этом слу­чае Вы долж­ны ис­поль­зо­вать те же самые ис­ход­ные дан­ные и пе­ре­мен­ные, какие были пред­ло­же­ны в при­ведённых фраг­мен­тах.

 

По­яс­не­ние.

Чтобы за один про­ход опре­де­лить ко­ли­че­ство чётных и нечётных эле­мен­тов и со­от­вет­ству­ю­щие им ми­ни­му­мы, нужны 5 пе­ре­мен­ных (два счётчика, два ми­ни­му­ма и ин­декс), а в усло­вии раз­ре­ше­но ис­поль­зо­вать толь­ко 4. Чтобы обой­ти это огра­ни­че­ние, за­ме­тим, что, по­сколь­ку общее ко­ли­че­ство эле­мен­тов из­вест­но, можно под­счи­ты­вать ко­ли­че­ство толь­ко в одной груп­пе. Эта идея ре­а­ли­зо­ва­на в сле­ду­ю­щем фраг­мен­те на языке Пас­каль.

Воз­мож­но также двух­про­ход­ное ре­ше­ние: на пер­вом про­хо­де опре­де­ля­ет­ся ко­ли­че­ство чётных и нечёных эле­мен­тов, на вто­ром опре­де­ля­ет­ся ми­ни­мум в со­от­вет­ству­ю­щей груп­пе. Эта идея ре­а­ли­зо­ва­на в сле­ду­ю­щем фраг­мен­те на ал­го­рит­ми­че­ском языке.

 

Пас­каль

j:=0; k:=10001; m:=10001;

for i:=1 to N do begin

if a[i] mod 2 = 0 then begin

j:=j+1;

if a[i] < k then k:=a[i];

end

else if a[i] < m then m:=a[i];

end;

if j <=n-j

then writeln(k)

else writeln(m);

 

Ал­го­рит­ми­че­ский язык

j:=0; k:=0

нц для i от 1 до N

если mod(a[i],2)=0

то j:=j+1

иначе k:=k+1

все

кц

если j <=k

то j:=0

иначе j:=1

все

m:=10001

нц для i от 1 до N

если mod(a[i],2) = j

то m := imin(m,a[i])

все

кц

вывод m

 

 

Категория: по информатике | Добавил: Просмотров: 1 | Теги: Ал­го­рит­мы обработки массивов | Рейтинг: 0.0/0
Всего комментариев: 0