Последовательность - C++

@Mayonez · Регистрация: 26.12.2009

Дано последовательность чисел 0 и 1
За какое минимальное количество перемещений её можно упорядочить так, чтобы сначала шли 0, а потом 1.
Перемещением считается вставка числа между двумя другими или с любого конца последовательности

Пример
6 ---------- элементов в последовательности
0
0
1
0
0
1
Ответ
1

valeriikozlov · 14.12.2010, 11:40

C

#include <stdio.h>
#include <string.h>
 
int main(int argc, char **argv)
{
    int N=6, l, r, mas[6]={0,0,1,0,0,1}, col=0, temp_l, temp_r;
    l=0; r=N-1;
    while(l<r-1)
    {
        while(mas[l]==0)
            l++;
        while(mas[r]==1)
            r--;
        if(l<r-1)
        {
            temp_l=l;
            temp_r=r;
            while(mas[temp_l]==1)
                temp_l++;
            while(mas[temp_r]==0)
                temp_r--;
            if(temp_l-l>r-temp_r)
            {
                col+=r-temp_r;
                r=temp_r;
            }
            else
            {
                col+=temp_l-l;
                l=temp_l;
            }
        }
    }
    printf("%d", col);
 
        return 0;
}

@Mr.X · 15.12.2010, 06:10

Сообщение от valeriikozlov

C

#include <stdio.h>
#include <string.h>
 
int main(int argc, char **argv)
{
    int N=6, l, r, mas[6]={0,0,1,0,0,1}, col=0, temp_l, temp_r;
    l=0; r=N-1;
    while(l<r-1)
    {
        while(mas[l]==0)
            l++;
        while(mas[r]==1)
            r--;
        if(l<r-1)
        {
            temp_l=l;
            temp_r=r;
            while(mas[temp_l]==1)
                temp_l++;
            while(mas[temp_r]==0)
                temp_r--;
            if(temp_l-l>r-temp_r)
            {
                col+=r-temp_r;
                r=temp_r;
            }
            else
            {
                col+=temp_l-l;
                l=temp_l;
            }
        }
    }
    printf("%d", col);
 
        return 0;
}

Программа такое выводит:

100010
1

Для продолжения нажмите любую клавишу . . .

и такое:

101111
0

Для продолжения нажмите любую клавишу . . .

Вроде бы это неправильно.

Добавлено через 1 час 15 минут
Вот так вроде бы правильно работает:

C++

//////////////////////////////////////////////////////////////////////////////////////
//Дано последовательность чисел 0 и 1
//За какое минимальное количество перемещений её можно упорядочить так, 
//чтобы сначала шли 0, а потом 1.
//Перемещением считается вставка числа между двумя другими или с любого конца 
//последовательности
//
//Пример
//6 ---------- элементов в последовательности
//0
//0
//1
//0
//0
//1
//Ответ
//1 
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    srand(static_cast<unsigned>(time(0)));   
 
    struct  T_rand_0_1_symb
    {
        char  operator() ()
        {
            return rand() % 2 + '0';
        }
    };
    int    k = rand() % 10 + 2;
    T_str  s(k, 0);
 
    std::generate(s.begin(), s.end(), T_rand_0_1_symb());
    T_str             ss(s);       
    T_str::size_type  pos_cur  = 0;
    int               n        = 0;
    
    while(    
             (pos_cur = s.find("10")) != T_str::npos
         )
    {
        ++n;
        s.replace(pos_cur, 2, "");
    }
    std::cout << ss
              << std::endl
              << n
              << std::endl;
}

valeriikozlov · 15.12.2010, 06:10

Сообщение от Mr.X

101111
0
Для продолжения нажмите любую клавишу . . .
Вроде бы это неправильно.

Да действительно неправильно. Тогда вот так:

C

#include <stdio.h>
#include <string.h>
 
int main(int argc, char **argv)
{
        int N=6, l, r, mas[6]={0,0,1,0,0,1}, col=0, temp_l, temp_r;
        l=0; r=N-1;
        while(l<r-1)
        {
                while(mas[l]==0)
                        l++;
                while(mas[r]==1)
                        r--;
                if(l<r)
                {
                        temp_l=l;
                        temp_r=r;
                        while(mas[temp_l]==1)
                                temp_l++;
                        while(mas[temp_r]==0)
                                temp_r--;
                        if(temp_l-l>r-temp_r)
                        {
                                col+=r-temp_r;
                                r=temp_r;
                        }
                        else
                        {
                                col+=temp_l-l;
                                l=temp_l;
                        }
                }
        }
        printf("%d", col);
 
        return 0;
}

@Mayonez 380 / 272 / 21 Регистрация: 26.12.2009 Сообщений: 875
		#1
	Последовательность - C++ 13.12.2010, 21:20. Просмотров 335. Ответов 3 Метки нет (Все метки) Дано последовательность чисел 0 и 1 За какое минимальное количество перемещений её можно упорядочить так, чтобы сначала шли 0, а потом 1. Перемещением считается вставка числа между двумя другими или с любого конца последовательности Пример 6 ---------- элементов в последовательности 0 0 1 0 0 1 Ответ 1 0

	15.12.2010, 06:10

Опции темы

С++ для начинающих

Последовательность - C++