VPF::[C++]Перестановки в антилексикографическом порядке

Vampire551

Дата 21.5.2008, 15:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.5.2008

Репутация: нет
Всего: нет

Допишите пожалуйста прогу так чтобы она отбирала "хорошие" перестановки и записывала их в массив. "Хорошие" перестановки - это если перестановку разбить на 2 части то сумма цифр в левой части должна быть равна или примерно равна сумме цифр в правой части. Например: ряд (1 2 3 4), "хорошие" перестановки - (1 4 2 3),(1 4 3 2),(2 3 1 4), (3 2 1 4), (2 3 4 1), (4 1 3 2 ), (4 1 2 3). Заранее благодарен. smile

Код


#include <stdio.h>
#include <conio.h>
#include<iostream.h>

#define N 4

void swap(int *a, int *b)
{
  int t;
  t=*a;
  *a=*b;
  *b=t;
}

void reverse(int * P,int m)
{
  int i=0, j=m;
  while(i<j)
 {
   swap(&P[i], &P[j]);
   i++;
   j--;
 }
}

void antilex(int * P,int m)
{
  int i;
  if(m==0)
 {
  for(i=0; i<N; i++)
  printf("%d ",P[i]);
  printf("\n");
 }
else
{
  for(i=0; i<=m; i++)
 {
   antilex(P,m-1);
   if(i<m)
  {
    swap(&P[i], &P[m]);
    reverse(P,m-1);
  }
 }
}
}

void main()
{
 clrscr();
 int i;
 int P[N];
 for(i=0; i<N; i++)
 P[i] = i+1;
 antilex(P,N-1);
 getch();
}

M
Rodman

Модератор: Название темы должно содержать язык написания!

Это сообщение отредактировал(а) Rodman - 21.5.2008, 15:14

Rififi

Дата 21.5.2008, 15:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 4
Всего: 36

Цитата(Vampire551 @ 21.5.2008, 15:01

)

сумма цифр в левой части должна быть равна или примерно равна сумме цифр в правой части

и насколько "примерно"?

Vampire551

Дата 21.5.2008, 16:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.5.2008

Репутация: нет
Всего: нет

Если сможете сделайте пожалуйста только с равно. Про "примерно" надо уточнить у препода, там вроде еще какое то условие есть. Заранее спасибо. smile

Rififi

Дата 21.5.2008, 16:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 4
Всего: 36

Компилировать компилятором, который знаком со стандартной библиотекой шаблоновне по наслышке (Visual C++ 6.0 и выше, Borland C++ Builder, ...)

Код

#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <vector>
#include <stdexcept>

template <typename T, const size_t N>
static void show_permutes(const T (&arr_p)[N])
{
    // число элементов должно быть чётным
    if (N & 1)
        throw std::runtime_error("Нечётное количество элементов в массиве");

    // делаем копию массива
    T arr[N];
    std::copy(arr_p, arr_p+N, arr);

    // Индекс "половинного элемента"
    const size_t half = N / 2;
    
    // Итератор для вывода на консоль
    std::ostream_iterator<T> output(std::cout, " ");
    
    // Ищем среди всех возможных перестановок...
    while(std::next_permutation(arr, arr+N))
    {
        // ... только те, у которых равны суммы левой и правой половинок
        if (std::accumulate(arr, arr+half, T()) == std::accumulate(arr+half, arr+N, T()))
        {
            // И выводим их на консоль
            std::copy(arr, arr+N, output);
            std::cout << std::endl;
        }
    }
}

int main()
{
    int arr[] = {1,2,3,4};
    show_permutes(arr);
    return (0);
}

Результат:

Код

Vampire551

Дата 21.5.2008, 17:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.5.2008

Репутация: нет
Всего: нет

Спасибо большое за программу. Но мне нужно было доделать мою прогу (просто нужен именно тот алгоритм, перестановки в антилексикографическом порядке). smile

Помогите пожалуйста. Заранее благодарен.

t_gran

Дата 22.5.2008, 06:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Цитата

Но мне нужно было доделать мою прогу

Доделать, так доделать. smile

А самому?

Код


#include <stdio.h>    

#define N 4    
//-----------------------------------------------//
void swap (int *a, int *b)    
{    
   int t;
   t= *a;
   *a= *b;
   *b= t;
}    
//-----------------------------------------------//
void reverse (int *P, int m)
{    
   int i= 0, j= m;
   while (i < j)
   {
      swap (&P[i], &P[j]);
      i++;
      j--;
   }
}    
//-----------------------------------------------//
void antilex (int *P, int m)    
{    
   int i;    
   if (m == 0)
   {
      int sumL= 0, sumR= 0;
      for (i= 0; i < N / 2; i++)
         sumL+= P[i];
      for (; i < N; i++)
         sumR+= P[i];
      if (sumL == sumR)
      {
         for (i= 0; i < N; i++)
            printf ("%d ", P[i]);
         printf("\n");
      }
   }
   else
   {
      for (i= 0; i <= m; i++)
      {
         antilex (P, m - 1);
         if (i < m)
         {
            swap (&P[i], &P[m]);
            reverse (P, m - 1);
         }
      }
   } // else if (m == 0)
}
//-----------------------------------------------//
int main()    
{    
   int i;
   int P[N];
   for (i= 0; i < N; i++)
      P[i]= i + 1;
   antilex (P, N - 1);
   return 0;
}

Это сообщение отредактировал(а) t_gran - 22.5.2008, 06:31

--------------------

Vampire551

Дата 22.5.2008, 11:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.5.2008

Репутация: нет
Всего: нет

Спасибо огромное за программу. smile

t_gran

Дата 23.5.2008, 03:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Vampire551, тогда помечай тему как закрытую.

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »