Ре­ше­ния за­дач по про­грам­ми­ро­ва­нию

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

За­да­ча 1

Усло­вие

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

Оцен­ка:

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

Ре­ше­ние

Вна­ча­ле на­ив­ный ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N^2\right):

int main(void)
{
    int const A[] = {4, 3, 2, 1}; //Исходный массив
    int const N = sizeof(A) / sizeof(*A); //Число элементов исходного массива
    int B[N]; //Результирующий массив
   
    for(int b = 0; b < N; ++b) //Перебираем все элементы результирующего массива
    {
        int p = 1; //Каждый результирующий элемент равен произведению всех
        for(int a = 0; a < N; ++a) //исходных элементов, кроме того, что
            if(a != b) p *= A[a];  //находится на месте результирующего
        B[b] = p;
    }
   
    //В массиве B находится результат

    return 0;
}

Как вы­чис­лить быст­рее? Да очень про­сто! За­ме­тим, что у нас каж­дый эле­мент ра­вен про­из­ве­де­нию всех ис­ход­ных эле­мен­тов, что сле­ва, на все ис­ход­ные эле­мен­ты, что спра­ва. Все «ле­вые» про­из­ве­де­ния мо­гут быть по­счи­та­ны од­ним цик­лом сле­ва-на­пра­во, все пра­вые про­из­ве­де­ния — од­ним цик­лом спра­ва-на­ле­во. Ре­зуль­та­ты од­но­го из цик­лов мож­но вре­мен­но со­хра­нить пря­мо в мас­си­ве B. В ито­ге по­лу­ча­ем ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N\right):

int main(void)
{
    int const A[] = {4, 3, 2, 1}; //Исходный массив
    int const N = sizeof(A) / sizeof(*A); //Число элементов исходного массива
    int B[N]; //Результирующий массив
   
    int p = 1; //Вначале в массив B записываем лишь «левые» произведения
    for(int i = 0; i < N; ++i) { B[i] = p; p *= A[i]; }
    p = 1; //Потом считаем правые произведения, и домножаем на них элементы B
    for(int i = N-1; i >= 0; --i) { B[i] *= p; p *= A[i]; }
   
    //В массиве B находится результат

    return 0;
}

За­да­ча 2

Усло­вие

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

Оцен­ка:

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

Ре­ше­ние

Да­вай­те вспом­ним, как мы скла­ды­ва­ем в стол­бик. Мы рас­по­ла­га­ем чис­ла друг под дру­гом так, что­бы их пра­вые края (млад­шие раз­ря­ды) сов­па­да­ли. За­тем идём спра­ва-на­ле­во, сум­ми­руя циф­ры. Ес­ли по­лу­ча­ет­ся дву­знач­ный ре­зуль­тат, то стар­шая циф­ра идёт в пе­ре­нос («в уме»), млад­шая — в ре­зуль­тат.

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

Итак, раз­ря­ды в ис­ход­ных чис­лах и ре­зуль­та­те ну­ме­ру­ют­ся спра­ва-на­ле­во. Ес­ли мас­сив A име­ет раз­мер N, то по­лу­чить его эле­мент по но­ме­ру i спра­ва (на­чи­ная с ну­ля) мож­но при по­мо­щи вы­ра­же­ния A[N-1-i].

При вы­во­де ре­зуль­та­та на экран мы пе­ча­та­ем циф­ры сле­ва-на­пра­во, про­пус­кая иду­щие в на­ча­ле ну­ли (ес­ли есть). Циф­ры, боль­шие, чем 9, вы­во­дят­ся бук­ва­ми A, ... , Z:

#include <iostream>

int main(void)
{
    int const base = 10; //Основание системы счисления
    //Цифры слагаемых в виде массивов цифр:
    int const A[] =    {1, 2, 3}; int const nA = sizeof(A) / sizeof(*A);
    int const B[] = {9, 9, 8, 5}; int const nB = sizeof(B) / sizeof(*B);
    //Результат может быть на один разряд длиннее самого длинного из слагаемых:
    int const nC( nA>nB ? nA+1 : nB+1 ); int C[nC];

    int carry = 0; //Перенос
    for(int i = 0; i < nC; ++i) //i — номер текущей цифры (справа-налево)
    {
        //Недостающие (слева) цифры каждого слагаемого полагаются равными нулю:
        int const a = i < nA ? A[nA - 1 - i] : 0;
        int const b = i < nB ? B[nB - 1 - i] : 0;
        int const c = a + b + carry; //Сумма двух цифр и переноса с младших разрядов
        C[nC - 1 - i] = c % base; //Правая цифра суммы записывается в результат
        carry = c / base; //Левая цифра суммы идёт в перенос
    }

    //Вывод на экран с пропуском лидирующих нулей
    bool nonZero = false;
    for(int i = 0; i < nC; ++i)
    {
        nonZero = nonZero || C[i];
        if(nonZero)
        {
            if(C[i] < 10) std::cout << C[i];
            else std::cout << char('A' + C[i] - 10);
        }
    }
    if(!nonZero) std::cout << '0'; //Ничего не вывели (все нули). Выводим ноль
    std::cout << std::endl;

    return 0;
}

За­да­ча 3

Усло­вие

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

Оцен­ка:

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

Ре­ше­ние

За­да­ча о пе­ре­ме­ши­ва­нии эле­мен­тов мас­си­ва в ка­ком-то смыс­ле клас­си­че­ская. Ко­гда-то (не знаю, как сей­час) в школь­ных учеб­ни­ках по ин­фор­ма­ти­ке мож­но бы­ло най­ти сле­дую­щий (очень пло­хой) ал­го­ритм:

  • Бе­рём ну­ле­вой эле­мент ис­ход­но­го мас­си­ва и ста­вим его в слу­чай­ное ме­сто ре­зуль­ти­рую­ще­го мас­си­ва.
  • Бе­рём сле­дую­щий эле­мент ис­ход­но­го мас­си­ва и пы­та­ем­ся по­ста­вить его в слу­чай­ное ме­сто ре­зуль­ти­рую­ще­го мас­си­ва. Ес­ли ме­сто ока­за­лось за­ня­то, пы­та­ем­ся по­ста­вить эле­мент в ка­кое-ни­будь дру­гое слу­чай­ное ме­сто, и так да­лее, по­ка не на­ткнём­ся на сво­бод­ное ме­сто;
  • По­вто­ря­ем преды­ду­щий пункт, по­ка все эле­мен­ты ис­ход­но­го мас­си­ва не бу­дут рас­став­ле­ны.

Ис­ход­ный код:

#include <cstdlib>

int main(void)
{
    int const A[] = {8, 7, 6, 5, 4, 3, 2, 1}; int const N = sizeof(A) / sizeof(*A);
    int B[N]; //Сюда будем класть элементы в случайном порядке

    for(int i = 0; i < N; ++i) B[i] = 0; //«Пустые» места будем помечать нулём

    for(int i = 0; i < N; ++i)
    { //Ставим все элементы
        while(true)
        { //Выбираем случайное место. Если пусто, ставим туда элемент
            int const pos = std::rand() % N;
            if( !B[pos] ) { B[pos] = A[i]; break; }
        }
    }

    //В массиве B лежат элементы из A, расположенные в случайном порядке

    return 0;
}

Ин­те­рес­но, что в пред­став­лен­ном вы­ше ал­го­рит­ме со­вер­шен­но не­важ­но, ка­ким чис­лом по­ме­чать «пу­стые» эле­мен­ты мас­си­ва. Нет ни­че­го страш­но­го в том, что это чис­ло сов­па­дёт с од­ним или не­сколь­ки­ми эле­мен­та­ми ис­ход­но­го мас­си­ва (по­ду­май­те, по­че­му). По­это­му «пу­стым» вы­бран ноль; его про­ще все­го про­ве­рять в услов­ном опе­ра­то­ре if. В сред­нем ал­го­ритм ра­бо­та­ет за вре­мя O\left(N^2\right), так как чис­ло по­пы­ток, ко­то­рое в сред­нем нуж­но сде­лать, что­бы по­ста­вить эле­мент в ре­зуль­ти­рую­щий мас­сив, про­пор­цио­наль­но по­зи­ции это­го эле­мен­та в ис­ход­ном мас­си­ве. Кро­ме то­го, ес­ли ге­не­ра­тор слу­чай­ных чи­сел не очень хо­ро­ший, ал­го­ритм мо­жет ра­бо­тать су­ще­ствен­но доль­ше, чем ожи­да­ет­ся.

Бо­лее быст­рый спо­соб пе­ре­ме­шать эле­мен­ты — это сфор­ми­ро­вать па­ры чи­сел, при­со­еди­нив к каж­до­му эле­мен­ту ис­ход­но­го мас­си­ва слу­чай­ное чис­ло, а за­тем от­сор­ти­ро­вать па­ры по воз­рас­та­нию их слу­чай­ной ком­по­нен­ты. При этом по­ря­док пар ста­но­вит­ся слу­чай­ным (по срав­не­нию с ис­ход­ным по­ряд­ком). Этот ал­го­ритм име­ет не­до­ста­ток, свя­зан­ный с тем, что слу­чай­ные чис­ла у не­ко­то­рых пар мо­гут ока­зать­ся рав­ны­ми. В этом слу­чае по­ря­док та­ких пар бу­дет опре­де­лять­ся ал­го­рит­мом сор­ти­ров­ки, и не бу­дет слу­чай­ным. Ес­ли слу­чай­ные чис­ла ге­не­ри­ру­ют­ся из боль­шо­го диа­па­зо­на (мно­го боль­ше­го, чем квад­рат ко­ли­че­ства эле­мен­тов; смот­ри­те Birthday Paradox), то «не­слу­чай­но­стью» мож­но пре­не­бречь.

Про­грам­ма мо­жет вы­гля­деть сле­дую­щим об­ра­зом (вре­мя ра­бо­ты — O\left(N\cdot \mathrm{ln}\left(N\right)\right)):

#include <cstdlib>
#include <algorithm>

struct pair
{ //Пара чисел для сортировки. Сортировка производится по второму числу
    int a, b;
    bool operator<(pair const &p) { return b < p.b; }
};

int main(void)
{
    int A[] = {8, 7, 6, 5, 4, 3, 2, 1}; int const N = sizeof(A) / sizeof(*A);
    pair B[N]; //Массив пар

    //Первое число — число из исходного массива. Второе — случайное
    for(int i = 0; i < N; ++i) { B[i].a = A[i]; B[i].b = std::rand(); }

    std::sort(B, B + N); //Сортируем

    for(int i = 0; i < N; ++i) A[i] = B[i].a; //Копируем обратно
   
    //Теперь элементы массива A перемешаны

    return 0;
}

На­ко­нец, при­ве­ду са­мый быст­рый ал­го­ритм, ра­бо­таю­щий за вре­мя O\left(N\right), да ещё и не тре­бую­щий до­пол­ни­тель­ных мас­си­вов. Ал­го­ритм от­ли­ча­ет­ся от пер­во­го (са­мо­го мед­лен­но­го) тем, что не «каж­дый эле­мент ста­вит­ся в слу­чай­ное ме­сто», а «на каж­дое ме­сто ста­вит­ся слу­чай­ный эле­мент». В этом слу­чае нам не нуж­но ис­кать сво­бод­ные ме­ста для эле­мен­тов.

С дру­гой сто­ро­ны, воз­ни­ка­ет про­бле­ма, что один и тот же эле­мент мо­жет быть взят не­сколь­ко раз. Что­бы это­го не про­изо­шло, эле­мен­ты нуж­но уби­рать из ис­ход­но­го мас­си­ва. Ес­ли нам взду­ма­ет­ся для ре­ше­ния этой про­бле­мы по­ме­чать эле­мен­ты, как «взя­тые», то мы вы­нуж­де­ны бу­дем ис­кать «не взя­тый» эле­мент, и сно­ва при­дём к мед­лен­но­му ал­го­рит­му, ра­бо­таю­ще­му за O\left(N^2\right). Что­бы это­го не про­изо­шло, эле­мен­ты долж­ны оста­вать­ся вплот­ную друг к дру­гу. Это­го мож­но до­бить­ся, пе­ре­ме­щая пер­вый «не взя­тый» эле­мент на ме­сто «взя­то­го». Осво­бож­даю­щее­ся на­ча­ло мас­си­ва мож­но ис­поль­зо­вать для хра­не­ния ре­зуль­та­та. Ал­го­ритм:

  • Бе­рём пер­вый эле­мент и об­ме­ни­ва­ем его с эле­мен­том, чей но­мер \geqslant 1 (воз­мож­но, эле­мент об­ме­ня­ет­ся сам с со­бой);
  • Бе­рём вто­рой эле­мент и об­ме­ни­ва­ем его с эле­мен­том, чей но­мер \geqslant 2 (воз­мож­но, эле­мент об­ме­ня­ет­ся сам с со­бой);
  • Ана­ло­гич­но де­ла­ем для осталь­ных эле­мен­тов, кро­ме по­след­не­го (по­след­ний не тро­га­ем).

Про­грам­ма:

#include <cstdlib>
#include <algorithm>

int main(void)
{
    int A[] = {8, 7, 6, 5, 4, 3, 2, 1}; int const N = sizeof(A) / sizeof(*A);

    for(int i(0); i < N-1; ++i) std::swap( A[i], A[ i + rand() % (N-i) ] );

    //Массив A перемешан. Красивый алгоритм, не правда ли?

    return 0;
}

Ин­те­рес­но, что пред­став­лен­ный вы­ше ал­го­ритм име­ет­ся в стан­дарт­ной биб­лио­те­ке C++ (на­зы­ва­ет­ся std::random_shuffle), но я бы не при­нял та­кое ре­ше­ние:

#include <algorithm>

int main(void)
{
    int A[] = {8, 7, 6, 5, 4, 3, 2, 1}; int const N = sizeof(A) / sizeof(*A);

    std::random_shuffle(A, A + N);

    return 0;
}

За­да­ча 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 бал­лов.

Ре­ше­ние

На­ив­ный ал­го­ритм за­клю­ча­ет­ся в том, что мы пе­ре­би­ра­ем все сим­во­лы стро­ки A, и для каж­до­го сим­во­ла пе­ре­би­ра­ем все сим­во­лы B. Ес­ли най­де­но сов­па­де­ние, то вы­во­дим сим­вол из стро­ки A и за­вер­ша­ем по­иск в стро­ке B (что­бы, ес­ли об­на­ру­жит­ся вто­рое сов­па­де­ние, сим­вол из A не вы­вел­ся по­втор­но. Про­грам­ма:

#include <string>
#include <iostream>

int main(void)
{
    std::string const A = "Anton", B = "nA";

    for(int a = 0; a < A.length(); ++a)
    {
        for(int b = 0; b < B.length(); ++b)
        {
            if( A[a] == B[b] ) { std::cout << A[a]; break; }
        }
    }
    std::cout << std::endl;

    return 0;
}

Уско­рить про­грам­му мож­но раз­ны­ми спо­со­ба­ми. Ес­те­ствен­но, мы долж­ны пе­ре­брать все сим­во­лы стро­ки A, так как они по­тен­ци­аль­но мо­гут быть вы­ве­де­ны на экран. А вот по­иск в стро­ке B мож­но уско­рить. Ес­ли пред­по­ло­жить, что воз­мож­ное чис­ло раз­лич­ных сим­во­лов мно­го мень­ше дли­ны стро­ки B (на­при­мер, вто­рая стро­ка со­сто­ит из ты­сяч сим­во­лов, а раз­лич­ных сим­во­лов не бо­лее 256), то ра­цио­наль­но вна­ча­ле за­пом­нить, ка­кие сим­во­лы в стро­ке B есть, а за­тем ис­поль­зо­вать эту ин­фор­ма­цию для пе­ча­ти сим­во­лов из стро­ки A.

В свя­зи с тем, что про­грам­ма долж­на ра­бо­тать на лю­бом ком­пи­ля­то­ре C++, удо­вле­тво­ряю­щем стан­дар­там, нуж­но об­ра­тить вни­ма­ние на то, что нам не­из­ве­с­тен диа­па­зон из­ме­не­ния ти­па char, из ко­то­ро­го со­сто­ит std::string. Мы да­же не зна­ем, зна­ко­вый это тип, или без­зна­ко­вый. На по­мощь при­хо­дит стан­дарт­ный за­го­ло­воч­ный файл <climits>, со­дер­жа­щий не­об­хо­ди­мые кон­стан­ты CHAR_MIN и CHAR_MAX:

#include <string>
#include <climits>
#include <iostream>

int main(void)
{
    std::string const A = "Anton", B = "nA";

    bool symbols[CHAR_MAX - CHAR_MIN + 1]; //Здесь будем хранить, какие символы есть
    for(int i = 0; i <= CHAR_MAX - CHAR_MIN; ++i) symbols[i] = false;

    //Перебираем все символы строки B, запоминаем, какие есть:
    for(int b = 0; b < B.length(); ++b) symbols[B[b] - CHAR_MIN] = true;

    //Перебираем все символы строки A, печатаем только те, что есть в B
    for(int a = 0; a < A.length(); ++a)
        if( symbols[A[a] - CHAR_MIN] ) std::cout << A[a];

    std::cout << std::endl;

    return 0;
}

Пред­став­лен­ная вы­ше про­грам­ма ра­бо­та­ет за вре­мя O\left(M+N\right) при усло­вии, что диа­па­зон из­ме­не­ния ти­па char мень­ше, чем N.

На­ко­нец, при­ве­ду про­грам­му, эф­фек­тив­но ра­бо­та­ю­щую при ма­лых раз­ме­рах строк A и B. Её идея в том, что мы сор­ти­ру­ем сим­во­лы в стро­ке B по воз­рас­та­нию, бла­го­да­ря че­му мо­жем за ло­га­риф­ми­че­ское вре­мя про­ве­рить су­ще­ство­ва­ние сим­во­ла в этой стро­ке:

#include <string>
#include <algorithm>
#include <iostream>

int main(void)
{
    std::string const A = "Anton"; std::string B = "nA";

    std::sort( B.begin(), B.end() ); //Сортирую символы в строке

    //Перебираем все символы строки A, печатаем только те, что есть в B
    //  наличие определяем быстрым двоичным поиском в отсортированном массиве
    for(int a = 0; a < A.length(); ++a)
        if( std::binary_search( B.begin(), B.end(), A[a] ) ) std::cout << A[a];

    std::cout << std::endl;

    return 0;
}

Сор­ти­ров­ка ра­бо­та­ет за вре­мя O\left(N\cdot\mathrm{ln}\left(N\right)\right), каж­дый по­иск ра­бо­та­ет за вре­мя O\left(\mathrm{ln}\left(N\right)\right), по­это­му об­щее вре­мя ра­бо­ты про­грам­мы: O\left(\left(M+N\right)\cdot\mathrm{ln}\left(N\right)\right), что, на пер­вый взгляд, мед­лен­нее, чем вре­мя ра­бо­ты преды­ду­щей про­грам­мы. Од­на­ко, про­грам­ма бу­дет ра­бо­тать быст­рее, чем преды­ду­щая, при не­боль­шом чис­ле (ме­нее 50) сим­во­лов в стро­ках A и B.

За­да­ча 5

Усло­вие

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

Оцен­ка:

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

Ре­ше­ние

Это очень про­стая за­да­ча. «Из­ме­не­ни­ем раз­ме­ра» сим­во­ла на­зо­вём пре­вра­ще­ние ма­лой бук­вы в за­глав­ную, а за­глав­ную — в ма­лую. Ал­го­ритм (с од­ним цик­лом):

  • Ме­ня­ем ме­ста­ми пер­вый и по­след­ний сим­во­лы стро­ки. Из­ме­ня­ем раз­ме­ры пер­во­го и по­след­не­го сим­во­лов.
  • Ме­ня­ем ме­ста­ми вто­рой и пред­по­след­ний сим­во­лы стро­ки, из­ме­ня­ем их раз­ме­ры.
  • Про­дол­жа­ем до тех пор, по­ка не дой­дём до се­ре­ди­ны стро­ки.

Ес­ли стро­ка со­сто­ит из не­чёт­но­го чис­ла сим­во­лов, то раз­мер цен­траль­но­го сим­во­ла сле­ду­ет из­ме­нять толь­ко один раз, по­это­му та­кой слу­чай дол­жен быть об­ра­бо­тан от­дель­но.

Так как «из­ме­не­ние раз­ме­ра» сим­во­ла встре­ча­ет­ся в не­сколь­ких ме­стах ал­го­рит­ма, то при про­грамм­ной реа­ли­за­ции ра­зум­но его вы­де­лить в от­дель­ную функ­цию. Идея ра­бо­ты функ­ции в том, что сим­во­лы с ко­да­ми 65, ... , 90 долж­ны отоб­ра­жать­ся в сим­во­лы с ко­да­ми 97, ... , 122, и на­обо­рот (под­ра­зу­ме­ва­ет­ся ко­ди­ров­ка ASCII).

Про­грам­ма:

#include<string>

void changeCase(char &c)
{ //Функция «изменяет размер» буквы английского алфавита
    if(c <= 90) c += 32; else c -= 32;
}

int main(void)
{
    std::string S = "Anton";

    for(int i = 0; i < S.length()/2; ++i)
    {
        std::swap( S[i], S[S.length() - i - 1] ); //Меняем местами две буквы
        changeCase( S[i] );                  //Меняем размер левой буквы
        changeCase( S[S.length() - i - 1] ); //Меняем размер правой буквы
    }

    //Если есть центральная буква, её размер тоже меняем:
    if(S.length() % 2) changeCase( S[S.length() / 2] );

    //Теперь в строке S результат

    return 0;
}

За­да­ча 6

Усло­вие

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

Оцен­ка:

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

Ре­ше­ние

Вна­ча­ле, как все­гда, не­опти­маль­ное ре­ше­ние. Его идея в том, что для каж­до­го эле­мен­та из пер­во­го мас­си­ва про­ве­ря­ет­ся его су­ще­ство­ва­ние во вто­ром мас­си­ве (по ана­ло­гии с за­да­чей 4). За­да­ча про­ще чет­вёр­той тем, что мас­си­вы уже от­сор­ти­ро­ва­ны (бу­дем ис­поль­зо­вать дво­ич­ный по­иск), но слож­нее её тем, что при вы­во­де нуж­но ис­клю­чить по­вто­ряю­щие­ся эле­мен­ты (они идут под­ряд, по­это­му мо­гут быть ис­клю­че­ны срав­не­ни­ем эле­мен­та с преды­ду­щим, ес­ли он есть). По­лу­ча­ем про­грам­му, ра­бо­та­ю­щую за вре­мя O\left(M\cdot \mathrm{ln}\left(N\right)\right):

#include <algorithm>
#include <iostream>

int main(void)
{
    int const A[] = {1,2,3,3,3,4,5,6}    ; int const M = sizeof(A)/sizeof(*A);
    int const B[] = {0,2,2,3,3,4,5,7,8,9}; int const N = sizeof(B)/sizeof(*B);

    for(int a = 0; a < M; ++a)
    {
        if( a && A[a] == A[a-1] ) continue; //Если такой элемент был, то пропускаем
        //Проверяем наличие элемента во втором массиве, выводим, если есть:
        if( std::binary_search( B, B + N, A[a] ) ) std::cout << A[a] << " ";
    }

    return 0;
}

Для оп­ти­маль­но­го по быст­ро­дей­ствию ре­ше­ния этой за­да­чи мож­но ис­поль­зо­вать ал­го­ритм, ана­ло­гич­ный про­це­ду­ре слия­ния двух мас­си­вов (смот­ри­те ал­го­ритм 2). Упро­ще­ние это­го ал­го­рит­ма за­клю­ча­ет­ся в том, что ес­ли один из мас­си­вов за­кан­чи­ва­ет­ся, ал­го­ритм пре­кра­ща­ет­ся. Услож­не­ние за­клю­ча­ет­ся в том, что нуж­но вы­бра­сы­вать по­вто­ряю­щие­ся эле­мен­ты.

Про­грам­ма вы­гля­дит сле­дую­щим об­ра­зом:

#include <iostream>

int main(void)
{
    int const A[] = {1,2,3,3,3,4,5,6}    ; int const M = sizeof(A)/sizeof(*A);
    int const B[] = {0,2,2,3,3,4,5,7,8,9}; int const N = sizeof(B)/sizeof(*B);

    int a = 0, b = 0;
    while(a < M && b < N) //Пока ни один из массивов не закончился
    {
        if(A[a] < B[b]) //В первом массиве меньший элемент. Пропускаем его
            ++a;
        else if(A[a] > B[b]) //Во втором массиве меньший элемент. Пропускаем
            ++b;
        else //Равные элементы. Выводим
        {
            int const t = A[a];
            std::cout << t << " ";
            //Пропускаю потенциально существующую цепочку пар, равных t
            do { ++a; ++b; } while(a < M && b < N && A[a] == t && B[b] == t);
        }
    }

    return 0;
}

На этот ал­го­ритм очень по­хож ал­го­ритм std::set_intersection стан­дарт­ной биб­лио­те­ки, но он не уда­ля­ет по­вто­ряю­щие­ся эле­мен­ты. Для уда­ле­ния при­дёт­ся за­пи­сать ре­зуль­тат вы­зо­ва ал­го­рит­ма в про­ме­жу­точ­ный мас­сив, и до­пол­ни­тель­но вы­звать std::unique:

#include <iostream>
#include <algorithm>

int main(void)
{
    int const A[] = {1,2,3,3,3,4,5,6}    ; int const M = sizeof(A)/sizeof(*A);
    int const B[] = {0,2,2,3,3,4,5,7,8,9}; int const N = sizeof(B)/sizeof(*B);
    int C[M+N]; //Массив для хранения результата

    int *end = std::set_intersection(A, A+M, B, B+N, C);
    end = std::unique(C, end);

    for(int *elem(C); elem != end; ++elem)
        std::cout << *elem << " ";

    return 0;
}

29 отзывов на запись «Ре­ше­ния за­дач по про­грам­ми­ро­ва­нию»

За­да­ча 5 — ва­ше ре­ше­ние име­ет 3 цик­ла. S.length() — это цикл 1. Цикл об­ме­на это 2. И цикл вы­во­да это 3. Мож­но во­об­ще без цик­тов — че­рез ре­кур­сию
Вы­вод стро­ки на экран не яв­лял­ся ча­стью усло­вия. Со­от­вет­ствен­но, и в ре­ше­нии вы­во­да нет. S.length() — это не цикл, хо­тя стан­дарт и до­пус­ка­ет реа­ли­за­цию этой функ­ции че­рез цикл. Ес­ли есть со­мне­ния по по­во­ду S.length() — ис­поль­зуй­те S.end() - S.begin(). Эта кон­ст­рук­ция га­ран­ти­ро­ван­но ра­бо­та­ет за вре­мя O(1).
чо нах??
по­мо­ги­те по­жа­луй­ста ре­шить за­да­чу по ал­го­рит­мам и по­стро­ить блок схем! Пе­ревіри­ти чи мо­же ку­ля з радіусом r пролізти че­рез ром­бо­вид­ний отвір з діаго­на­ля­ми p і q
4 за­да­ча 2 ал­го­ритм
bool symbols[CHAR_MAX - CHAR_MIN + 1]; //Здесь будем хранить, какие символы есть
for(int i = 0; i <= CHAR_MAX - CHAR_MIN; ++i) symbols[i] = false;
нель­зя раз­ве так:
bool symbols[CHAR_MAX - CHAR_MIN + 1] = 0;
?
То­гда уж
bool symbols[CHAR_MAX - CHAR_MIN + 1] = {0};
или, луч­ше
bool symbols[CHAR_MAX - CHAR_MIN + 1] = {false};
int main(void)
{
     int const A[] = {4, 3, 2, 1}; //Исходный массив
     int const N = sizeof(A) / sizeof(*A); //Число элементов исходного массива
     int B[N]; //Результирующий массив
     int P = 1; // произведение      for(int i = 0; b &lt; N; ++i) // найдём произведение
         P *= A[i];
     
     for(int i = 0; i &lt; N; ++i) // найдём каждый элемент
         B[i] = P / A[i];      return 0;
}
Я вот так первую ре­шил в уме, по­ка чи­тал ори­ги­наль­ную ста­тью, им­хо, эле­гант­нее. Пя­тую то­же ре­шил в уме (по оп­ти­му­му) , тре­тью знал как ре­шать — дав­но ещё при­ду­мал сам, си­дя над усло­ви­ем, в 2 цик­ла за O(N) Вто­рую знал как ре­шать, но лень рас­пи­сы­вать да­же в уме. Чет­вер­тую — бы­ли те же мыс­ли на­счёт сор­ти­ров­ки плюс вве­де­ния до­псущ­но­сти ( а я дель­фист, по­это­му с се­том, сет ча­ров быст­рее мас­си­ва), но не до­бил, в го­ло­ве опять же. Ше­стую — то­же мыс­ли по­доб­ные бы­ли, но не до­бил. До­пол­ни­тель­ные за­да­чи, по идее, ре­шил бы , ко­ли при­пёр­ло, хо­тя мо­жет и не оп­ти­маль­но, но так лень вы­во­дить гео­мет­рию в фор­му­лы ))) Боль­шое спа­си­бо за за­да­чи — взял ста­тьи в ко­пил­ку.
>Не раз­ре­ша­ет­ся ис­поль­зо­вать опе­ра­цию де­ле­ния
>B[i] = P / A[i];
Genius.
По­мо­ги­те Ре­шить за­да­чу Вве­сти 3-мер­ный мас­сив це­лых чи­сел и сум­му всех не­чет­ных эл­ле­мен­тов , есть чет­ное чис­ло
По­мо­ги­те ре­шить за­да­чу. ..да­на по­сле­до­ва­тель­ность сим­во­лов.про­ве­рить яв­ля­ет­ся ли она це­лым чис­лом
по­мо­ги­те ре­шать по­жа­луй­ста! у ме­ня зав­тра эк­за­мен!
на­пи­ши­те функ­цию rightposition ко­то­рая по­лу­ча­ет два па­ра­мет­ра str1 и str2 ти­па string и воз­вра­ща­ет по­зи­цию на­ча­ла по­след­не­го по­яв­ле­ния str2 в str1. на­при­мер rightposition («мис­си­си­пи». «си») да­ет зна­че­ния 6
Здесь не по­мо­га­ют ре­шать за­да­чи. Со­жа­лею.
а вы са­ми смо­же­те?

По­па­лась ин­те­рес­ная за­дач­ка на cyberforum.ru

Дан це­ло­чис­лен­ная по­сле­до­ва­тель­ность a[3], a[4], ... , a[n-1], каж­дый член ко­то­рой не бо­лее 1000 по аб­со­лют­ной ве­ли­чи­не. Най­ди­те три чле­на, про­из­ве­де­ние ко­то­рых мак­си­маль­но.

Вро­де по­лу­чи­лось со­ста­вить ли­ней­ный ал­го­ритм. Вер­но ли ре­ше­ние?

#include <iostream>
using namespace std;
 
int main()
{
    int a[] = {3, 5, -9, 7, 8, 0, 1, -3, -10},
    n = sizeof(a) / sizeof(*a);
 
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
 
    for (int i = 0; i < 2; i++)       // Переносим в начале массива
    {                                 // 2 минимальных элемента (время ~O(n))
        int k = i;                    
        for (int j = i+1; j < n; j++)
        {
            if (a[j] < a[k]) k = j;
        }
        int t = a[i]; a[i] = a[k]; a[k] = t;
    }
 
    for (int i = n-1; i >= n-3; i--)  // Переносим в конец массива
    {                                 // 3 максимальных элемента (время ~O(n))
        int k = i;
        for (int j = i-1; j >= 0; j--)
        {
            if (a[j] > a[k]) k = j;
        }
        int t = a[i]; a[i] = a[k]; a[k] = t;
    }
 
    int x = a[n-3], y = a[n-2];
 
    if ( a[0] < 0 && a[n-1] > 0 && (a[0]*a[1] > a[n-2]*a[n-3]) )
    {
        x = a[0]; y = a[1];
    }
 
    cout << "\n\nThree numbers whose product is maximum:\n\n";
    cout << x << " " << y << " " << a[n-1] << "\n" << endl;
 
    return 0;
}
Я не на­шёл оши­бок в ва­шем ко­де, од­на­ко не мо­гу до­ка­зать его кор­рект­ность. Хо­чет­ся ве­рить, что в от­сор­ти­ро­ван­ном мас­си­ве ис­ко­мый от­вет — ли­бо про­из­ве­де­ние трёх мак­си­маль­ных чи­сел, ли­бо про­из­ве­де­ние двух ми­ни­маль­ных на мак­си­маль­ное.

Во­об­ще, с ис­поль­зо­ва­ни­ем стан­дарт­ных ал­го­рит­мов мож­но на­пи­сать ко­ро­че:

#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
 
int main() {
    int fb[] = {3, 5, -9, 7, 8, 0, 1, -3, -10}; //Массив
    int *fe = fb + sizeof(fb)/sizeof(int);      //Конец массива
    reverse_iterator<int *> rb(fe), re(fb);     //«Перевёрнутый» массив
   
    //В конце помещаем три максимальных элемента в возрастающем порядке:
    partial_sort(rb, rb+3, re, greater<int>());
    //В начало помещаем два минимальных элемента:
    if (fe-fb > 4) partial_sort(fb, fb+2, fe-3);
   
    int a(fb[0]), b(fb[1]), c(rb[2]), d(rb[1]), e(rb[0]);
    cout << "Result: "; //Результирующие числа отсортированы по возрастанию
    if (a * b * e > c * d * e) cout << a << " " << b << " " << e << endl;
    else                       cout << c << " " << d << " " << e << endl;
 
    return 0;
}

Пер­вая ча­стич­ная сор­ти­ров­ка сор­ти­ру­ет по убы­ва­нию пе­ре­вёр­ну­тый мас­сив (вы­чис­ля­ет пер­вые три эле­мен­та это­го пе­ре­вёр­ну­то­го мас­си­ва). При­ме­ни­тель­но к ори­ги­наль­но­му мас­си­ву это озна­ча­ет на­хож­де­ние трёх мак­си­маль­ных эле­мен­тов и рас­по­ло­же­ния их в кон­це. Та­кое из­вра­ще­ние с пе­ре­вёр­ну­тым мас­си­вом по­на­до­би­лось по­то­му, что ча­стич­ная сор­ти­ров­ка сор­ти­ру­ет от на­ча­ла до за­дан­но­го эле­мен­та; нет ва­ри­ан­та сор­ти­ров­ки, сор­ти­рую­щей от за­дан­но­го эле­мен­та и до кон­ца.

Вто­рая ча­стич­ная сор­ти­ров­ка на­хо­дит два ми­ни­маль­ных эле­мен­та. Хвост мас­си­ва ис­клю­чён из об­ра­бот­ки (на­пи­са­но fe-3), так как ча­стич­ная сор­ти­ров­ка не обя­за­на со­хра­нять по­ря­док эле­мен­тов, иду­щих по­сле сор­ти­ро­ван­ных. Услов­ный опе­ра­тор пе­ред этой сор­ти­ров­кой ну­жен для то­го, что­бы функ­ция не упа­ла, ко­гда fb+2 > fe-3 для мас­си­ва из трёх или из че­ты­рёх эле­мен­тов. Да и не нуж­но её вы­зы­вать для мас­си­ва из че­ты­рёх эле­мен­тов — ес­ли три мак­си­маль­ных эле­мен­та рас­по­ло­же­ны в кон­це, то чет­вёр­тый яв­но бу­дет ми­ни­маль­ный и в на­ча­ле.

По­иг­рать­ся с этим ко­дом мож­но здесь.

У ме­ня (Visual C++ 2010) не ком­пи­ли­ру­ет­ся ваш код(( пи­шет: error C2065: greater: не­объ­яв­лен­ный иден­тифи­ка­тор
Я не на­шёл оши­бок в ва­шем ко­де, од­на­ко не мо­гу до­ка­зать его кор­рект­ность.
Ка­кую кор­рект­ность вы име­е­те вви­ду?

Мож­но ещё #include<functional> до­ба­вить.

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

Ко­ро­че нуж­но обос­но­вать мат. часть.
Нуж­но по­ду­мать.
За­да­ча 6
Да­ны два от­сор­ти­ро­ван­ных мас­си­ва A и B раз­ме­ра­ми M и N со­от­вет­ствен­но. На­пи­сать функ­цию, ко­то­рая вы­во­дит на экран эле­мен­ты, при­сут­ствую­щие од­но­вре­мен­но в обо­их мас­си­вах. Вы­во­ди­мые эле­мен­ты не долж­ны по­вто­рять­ся, да­же ес­ли эле­мен­ты в ис­ход­ных мас­си­вах по­вто­ря­ют­ся.
Я бы сна­ча­ла сдви­нул уни­каль­ные эле­мен­ты A и B в их на­ча­ла.
Как-то так
#include
using namespace std; int main()
{
    int A[] = {1,2,3,3,3,4,5,6}    ; int const M = sizeof(A)/sizeof(*A);
    int B[] = {0,2,2,3,3,4,5,7,8,9}; int const N = sizeof(B)/sizeof(*B);
    int m = 1, n = 1, a = 0, b = 0;     for (int i = 1, t = A[0]; i < M; i++)  // Сдвигаем в начало массива A
     { if (A[i] != t)                      //  уникальные элементы (m-штук)
        { A[m++] = A[i]; t = A[i]; }
     }     for (int i = 1, t = B[0]; i < N; i++)  // Аналогично предыдущему
     { if (B[i] != t)
        { B[n++] = B[i]; t = B[i]; }
     }      
                                           
    while (a < m && b < n)
     { if (A[a] <B> B[b]) ++b;
       else cout << A[a++] << "  ";
     }     cout << "null");        
    return 0;
}
Оно не­вер­но отоб­ра­зи­ло код((
На­чи­ная с while, долж­но быть так
while (a \'мень­ше\' m && b \'мень­ше\' n)
{ if (A[ a ] \"мень­ше\" B[ b ]) ++a;
else if (A[ a ] \'боль­ше\' B[ b ]) ++b;
else cout \'мень­ше (2 ра­за)\' \" \" \'мень­ше (2 ра­за)\' A[ a++ ];
} cout \'мень­ше (2 ра­за)\' endl;
system(\"pause \'боль­ше\' null\");
return 0;
Толь­ко так смог(
Этот код
#include
using namespace std; int main()
{
    int A[] = {1,2,3,3,3,4,5,6}    ; int const M = sizeof(A)/sizeof(*A);
    int B[] = {0,2,2,3,3,4,5,7,8,9}; int const N = sizeof(B)/sizeof(*B);
    int m = 1, n = 1, a = 0, b = 0;     for (int i = 1, t = A[0]; i &lt; M; i++)  // Сдвигаем в начало массива A
     { if (A[i] != t)                      //  уникальные элементы (m-штук)
        { A[m++] = A[i]; t = A[i]; }
     }     for (int i = 1, t = B[0]; i &lt; N; i++)  // Аналогично предыдущему
     { if (B[i] != t)
        { B[n++] = B[i]; t = B[i]; }
     }      
                                           
    while (a &lt; m &amp;&amp; b &lt; n)
     { if (A[a] <B> B[b]) ++b;
       else cout &lt;&lt; A[a++] &lt;&lt; &quot;  &quot;;
     }     cout &lt; null");        
    return 0;
}
в кон­це так долж­на быть <!-- while (a < m && b < n)
{ if (A[ a ] B[ b ]) ++b;
else cout << A[ a++ ] << " ";
} cout < null\");
return 0; -->
Что-то часть ко­да по­па­да­ет. Как пра­виль­но по­стить код?
по­езд про­ехал t1 ч со ско­ро­стью v1 км / ч, t2 ч со ско­рост­но­го v2 i t3 ч со ско­ро­стью v3.
Опре­де­лить прой­де­ны пу­ти с раз­ной ско­ро­стью и весь путь
По­мо­ги­те ре­шить сле­ду­ю­щую за­да­чу на C++ : На вход по­да­ет­ся не­ко­то­рое ко­ли­че­ство тре­уголь­ни­ков и окруж­но­стей. От­сор­ти­ро­вать и вы­ве­сти их по воз­рас­та­нию пло­ща­дей.
ре­бя­та по­мо­ги­те ре­шить,бу­ду очень бла­го­дор­на!!!!Стро­ка S, в ко­то­ром сло­ва раз­де­ле­ны
про­бе­ла­ми и зна­ка­ми. Вво­дит­ся сло­во W. Из стро­ки S
сфор­ми­ро­вать но­вую стро­ку SN, в ко­то­ром все
сло­ва W за­пи­са­но за­глав­ны­ми бук­ва­ми
по­мо­ги­те ре­шить за­да­чу:по­стро­ить рас­пре­де­ле­ние тем­пе­ра­ту­ры в плос­кой ме­тал­ли­че­ской пла­сти­не при усло­вии,что каж­дая сто­ро­на на­гре­та до тем­пе­ра­ту­ры T1,T2,T3,T4.
Сроч­но нуж­но ре­шить за­да­чу на кур­со­вую не­мо­гу в ней разо­б­рат­ся(
Zamena ( s ) .
На­зна­че­ние : за­ме­ня­ет в стро­ке сим­во­лов s каж­дые три точ­ки — од­ной точ­кой . Функ­ция долж­на воз­вра­щать ко­ли­че­ство сде­лан­ных за­мен .

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

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

   

Можете использовать теги <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>