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

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

За­да­ча 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;
}

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

За­да­ча 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 каж­дые три точ­ки — од­ной точ­кой . Функ­ция долж­на воз­вра­щать ко­ли­че­ство сде­лан­ных за­мен .
Tablets For Sale Uk in Fort Hood .
If you desire to improve your knowledge only keep visiting this web site and be updated with the newest gossip posted here.
What’s up to every body, it’s my first pay a quick visit
of this blog; this web site contains remarkable and in fact good information designed for visitors.
Hmm is anyone else encountering problems with the pictures on this
blog loading? I’m trying to figure out if its a problem on my end or if it’s
the blog. Any suggestions would be greatly appreciated.
Hi there Dear, are you really visiting this web site regularly,
if so afterward you will definitely obtain good experience.

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

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

   

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