Кон­т­роль­ная ра­бо­та по про­грам­ми­ро­ва­нию

Се­год­ня про­вёл у сво­их обол­ту­сов (ма­ги­стран­ты, 5-й курс ТТИ ЮФУ) кон­т­роль­ную ра­бо­ту по про­грам­ми­ро­ва­нию. Пра­ви­ла иг­ры бы­ли сле­дую­щие:

  1. Каж­дый сту­дент тя­нет би­лет с за­да­чей. Ес­ли би­лет ему не нра­вит­ся, он мо­жет ре­шить од­ну из до­пол­ни­тель­ных за­дач, на своё усмот­ре­ние.

  2. Ос­нов­ные за­да­чи оце­ни­ва­ют­ся в 10 бал­лов каж­дая. За не­опти­маль­ное ре­ше­ние за­да­чи преду­смот­ре­но сни­же­ние оцен­ки; это ого­во­ре­но в усло­вии каж­дой за­да­чи.

  3. До­пол­ни­тель­ные за­да­чи оце­ни­ва­ют­ся в 11 бал­лов каж­дая. Они в пол­то­ра ра­за слож­нее ос­нов­ных, но оце­ни­ва­ют­ся все­го на бал до­ро­же, так как сту­дент мо­жет вы­брать се­бе до­пол­ни­тель­ную за­да­чу по вку­су.

В об­щем, до­пол­ни­тель­ные за­да­чи так ни­кто и не ре­шил. Ос­нов­ные за­да­чи бы­ли ре­ше­ны, но очень ту­го. Год на­зад я да­вал по­доб­ные за­да­чи пер­во­курс­ни­кам МФТИ, там всё это шло влёт.

Ос­нов­ные за­да­чи

Ре­ше­ния этих за­дач опуб­ли­ко­ва­ны здесь.

За­да­ча 1

(Эту за­да­чу я по­за­им­ство­вал у Гуг­ла)

Дан мас­сив A це­лых чи­сел (N штук). Нуж­но по­лу­чить но­вый мас­сив це­лых чи­сел B, в ко­то­ром каж­дый эле­мент ра­вен про­из­ве­де­нию всех эле­мен­тов ис­ход­но­го мас­си­ва, кро­ме то­го эле­мен­та, ко­то­рый на­хо­дит­ся на ме­сте ре­зуль­ти­рую­ще­го. Не раз­ре­ша­ет­ся ис­поль­зо­вать опе­ра­цию де­ле­ния. При­мер ра­бо­ты: {4, 3, 2, 1} → {6, 8, 12, 24}.

Оцен­ка:

  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N\right), и не ис­поль­зую­щий до­пол­ни­тель­ных мас­си­вов (кро­ме A и B) — 10 бал­лов;
  • ал­го­ритм, ра­бо­таю­щий мед­лен­нее, чем O\left(N\right), ли­бо ис­поль­зую­щий до­пол­ни­тель­ные мас­си­вы — 5 бал­лов.

За­да­ча 2

На­пи­сать про­грам­му сло­же­ния двух це­лых чи­сел «в стол­бик». Чис­ла за­да­ют­ся в про­грам­ме в ви­де двух мас­си­вов цифр.

Оцен­ка:

  • ал­го­ритм, скла­ды­ваю­щий чис­ла в лю­бой си­сте­ме счис­ле­ния — 10 бал­лов;
  • ал­го­ритм, скла­ды­ваю­щий чис­ла в де­ся­тич­ной си­сте­ме счис­ле­ния — 7 бал­лов.

За­да­ча 3

Дан мас­сив, со­дер­жа­щий N це­лых чи­сел. Нуж­но по­лу­чить но­вый мас­сив, ко­то­рый со­сто­ит из эле­мен­тов ис­ход­но­го мас­си­ва, рас­по­ло­жен­ных в слу­чай­ном по­ряд­ке.

Оцен­ка:

  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N\right) — 10 бал­лов;
  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N\cdot \mathrm{ln}\left(N\right)\right) — 9 бал­лов;
  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N^2\right) — 6 бал­лов.

За­да­ча 4

Да­ны две стро­ки A и B (char * или std::string на ва­ше усмот­ре­ние), имею­щие дли­ны M и N со­от­вет­ствен­но. На­пи­сать про­грам­му, ко­то­рая вы­во­дит на экран стро­ку A, про­пус­кая те сим­во­лы, ко­то­рых нет в B. При­мер: A=“Anton”, B=“nA”, ре­зуль­тат: “Ann”.

Оцен­ка:

  • ал­го­ритм, ра­бо­таю­щий быст­рее, чем O\left(M\cdot N\right) — 10 бал­лов;
  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(M\cdot N\right) — 5 бал­лов.

За­да­ча 5

Да­на стро­ка (std::string или char *), со­сто­я­щая из букв ан­глий­ско­го ал­фа­ви­та (a, ... , z, A, ... , Z). На­пи­ши­те функ­цию, ко­то­рая пе­ре­во­ра­чи­ва­ет эту стро­ку на­обо­рот, и при этом за­ме­ня­ет за­глав­ные бук­вы на ма­лые и на­обо­рот. При­мер ра­бо­ты: “Anton” → “NOTNa”.

Оцен­ка:

  • ал­го­ритм, не ис­поль­зую­щий до­пол­ни­тель­ные мас­си­вы, со­сто­я­щий из од­но­го цик­ла — 10 бал­лов;
  • ал­го­ритм, ис­поль­зую­щий до­пол­ни­тель­ные мас­си­вы, ли­бо со­дер­жа­щий бо­лее од­но­го цик­ла — 7 бал­лов.

За­да­ча 6

Да­ны два от­сор­ти­ро­ван­ных мас­си­ва A и B раз­ме­ра­ми M и N со­от­вет­ствен­но. На­пи­сать функ­цию, ко­то­рая вы­во­дит на экран эле­мен­ты, при­сут­ствую­щие од­но­вре­мен­но в обо­их мас­си­вах. Вы­во­ди­мые эле­мен­ты не долж­ны по­вто­рять­ся, да­же ес­ли эле­мен­ты в ис­ход­ных мас­си­вах по­вто­ря­ют­ся.

Оцен­ка:

  • ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(M+N\right) — 10 бал­лов;
  • ал­го­ритм, ра­бо­таю­щий мед­лен­нее, чем O\left(M+N\right) — 5 бал­лов.

До­пол­ни­тель­ные за­да­чи

За­да­ча Д1

(Это ма­те­ма­ти­че­ская за­да­ча для тех, у ко­го ту­го с про­грам­ми­ро­ва­ни­ем)

На плос­ко­сти за­да­на окруж­ность (ко­ор­ди­на­та­ми цен­тра X, Y и ра­ди­у­сом R) и пря­мая точ­ка­ми (X_1,Y_1) и (X_2,Y_2). Про­стран­ство под пря­мой за­кра­ше­но чёр­ным цве­том. Ка­кая пло­щадь чёр­но­го цве­та по­па­да­ет внутрь окруж­но­сти? На­пи­сать про­грам­му, вы­чис­ля­ю­щую это.

Оцен­ка: 11 бал­лов.

За­да­ча Д2

На­пи­сать про­грам­му пе­ре­мно­же­ния двух це­лых чи­сел «в стол­бик». Чис­ла за­да­ют­ся в про­грам­ме в ви­де двух мас­си­вов цифр. На экран дол­жен быть вы­ве­ден ре­зуль­тат вме­сте с про­ме­жу­точ­ны­ми дей­стви­я­ми («стол­бик»). Не раз­ре­ша­ет­ся поль­зо­вать­ся опе­ра­ци­ей умно­же­ния при вы­чис­ле­ни­ях. Ука­за­ние: со­здай­те и ис­поль­зуй­те таб­ли­цу умно­же­ния.

Оцен­ка:

  • ал­го­ритм, пе­ре­мно­жаю­щий чис­ла в лю­бой си­сте­ме счис­ле­ния — 11 бал­лов;
  • ал­го­ритм, пе­ре­мно­жаю­щий чис­ла в де­ся­тич­ной си­сте­ме счис­ле­ния — 8 бал­лов.

За­да­ча Д3

На плос­ко­сти да­ны не­сколь­ко кру­гов (\left(X_1,Y_1,R_1\right); \left(X_2,Y_2,R_2\right); … ; \left(X_N,Y_N,R_N\right)). Не­ко­то­рые из них пе­ре­се­ка­ют­ся с дру­ги­ми, не­ко­то­рые — нет. Нуж­но най­ти раз­мер (ко­ли­че­ство эле­мен­тов) мак­си­маль­но­го под­мно­же­ства кру­гов, меж­ду ко­то­ры­ми мож­но пе­рей­ти че­рез точ­ки пе­ре­се­че­ния.

Оцен­ка: 11 бал­лов.

Семь отзывов на запись «Кон­т­роль­ная ра­бо­та по про­грам­ми­ро­ва­нию»

Школь­ные за­да­чи-то, да­же не для стар­ше­класс­ни­ков.
Я не спо­рю. Про­сто сту­ден­ты у ме­ня сла­бые.
«Школь­ные за­да­чи» ? Не сме­ши­те лю­дей. Взять хо­тя­бы первую — ре­ше­ние ни ра­зу не три­ви­аль­но. Да и то что по­доб­ные за­да­чи за­да­ют на со­бе­се­до­ва­нии в гугл на­ме­ка­ет, что за­да­чи не про­стые.
Хо­чу по­бла­го­да­рить за ка­че­ствен­ное вы­пол­не­ние ра­бо­ты по про­грам­ми­ро­ва­нию! Спа­си­бо боль­шое за ин­ди­ви­ду­аль­ный под­ход и разъ­яс­не­ния! Ра­бо­ту по­лу­чил в та­ком ви­де, в ка­ком бы­ло не­об­хо­ди­мо! Бу­ду ре­ко­мен­до­вать!
Cheap Propecia
suhagra online
Prednisone Mail Order

Оставить отзыв

Жёлтые поля обязательны к заполнению

   

Можете использовать теги <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang=""> <div class=""> <span class=""> <br>