Примеры реализации поразрядной сортировки

Radix sort, MSD. Для char-строк. Ноль - конец строки. На основе рекурсии. Глубина рекурсии = длина строки + 1. В каждой рекурсии требуется память для размещения двух массивов указателей: StringItem* front[256], т.е. 2Кб;

//элемент списка
struct StringItem{
  const char* str; //указатель на строку
  StringItem* next;
};
 
//pList - начало списка указателей на строки
//iDigit - разряд, по которому сортирует
//возвращает указатель на первый элемент отсортированной последовательности
StringItem*  radix_sort_msd_for_string(StringItem* pList, unsigned int iDigit )
{
  // количество вариантов значения одного разряда (char)
  const int iRange = 256; 
 
  //массив bucket-ов (под-списков)
  StringItem* front[iRange]; 
  memset(front, 0, sizeof(front) );
 
  StringItem** ppNextItem[iRange]; 
  for (int i = 0; i < iRange; i++)
    ppNextItem[i]=&front[i];
 
  //разбиваем список на bucket-ты, в зависимости от значения разряда
  while (pList)
  {
    StringItem* temp = pList;
    pList=pList->next;
 
    temp->next=NULL; //отключаем от списка
 
    unsigned char c = (unsigned char)temp->str[iDigit];
    *ppNextItem[c]=temp;
    ppNextItem[c]=&temp->next;
  }
 
  //строим выходной список
  StringItem* pResult = NULL;
  StringItem** ppNext = &pResult;
 
  //нулевой bucket возвращаем весь - он уже отсортирован
  *ppNext = front[0];
  while (*ppNext)
    ppNext=&((*ppNext)->next);
 
  for (int i = 1; i < iRange; i++)
  {
    //пустые - пропускаем
    if ( !front[i] )
      continue;
 
    if (front[i]->next == NULL)// с одним элементом - сразу добавляем
      *ppNext = front[i];
    else    // остальные - на сортировку по следующему разряду
      *ppNext = radix_sort_msd_for_string(front[i], iDigit + 1);
 
    while (*ppNext)
      ppNext=&((*ppNext)->next);
  }
 
  return pResult;}

Программа для тестирования
void TestAlgorithm()
{
  // открываем, большой текстовый файл для теста
  ifstream file("demo.txt"); 
  if ( !file )
    return;
 
  //считываем все слова из файла в вектор
  istream_iterator<string> ii(file);
  istream_iterator<string> eos;
  vector<string> vecs(ii, eos);
 
  // заполняем список 
  StringItem* pList = NULL;
  StringItem** ppCurr = &pList;
  for ( unsigned int i=0 ; i<vecs.size(); i++)
  {
    *ppCurr = new StringItem();
    (*ppCurr )->str = vecs[i].c_str();
    (*ppCurr )->next = NULL;
    ppCurr = &(*ppCurr)->next;    
  }
 
  //сортируем
  pList = radix_sort_msd_for_string(pList, 0);
 
  //файл для вывода
  ofstream fo("out.txt");
  ostream_iterator<string> oo(fo," ");
 
  // в конце удаляем список
  while(pList)
  {
    oo = pList->str; // выводим в файл
    StringItem* tmp = pList;
    pList = pList->next;
    delete tmp;
  }
}

Вариант сортировки 32 битных unsigned int. Не самый быстрый.
void radix_int(unsigned* begin, int size, unsigned bit = 0x80000000)
{
    if (!bit)
        return;
 
    if (size < 2)
        return;
 
    int last = 0;
    for (int i = 0; i < size; i++)
    {
        if ((begin[i] & bit) == 0)
            swap(begin[last++], begin[i]);
    }
 
    radix_int(begin,      last,      bit >> 1);
    radix_int(begin+last, size-last, bit >> 1);
}

Вариант сортировки 8 битных char. Порядок обратный. Для правильного порядка необходимо копировать сначала нули, потом единицы...
int radix_8(char* bytes, const int bcount)
{
        char* oneArray = (char*)malloc(bcount);
        char* zeroArray = (char*)malloc(bcount);
        int numOnes;
        int numZeros;
 
        int mask = 1;
 
        for (int count = 0; count < 8; count++)
        {
                numOnes = 0;
                numZeros = 0;
 
                for (int index = 0; index < bcount; index++)
                {
                        char bt = bytes[index];
                        if (bt & mask)
                        {
                                oneArray[numOnes] = bt;
                                numOnes++;
                        }
                        else
                        {
                                zeroArray[numZeros] = bt;
                                numZeros++;
                        }
                }
 
                // копирование единиц
                memcpy(bytes, oneArray, numOnes);
 
                // копирование нолей
                memcpy(bytes + numOnes, zeroArray, numZeros);
 
                // изменение маски для проверки следующего бита
                mask <<= 1;
        }
        free(oneArray);
        free(zeroArray);
}

Добавлено: 29 Мая 2018 20:21:52 Добавил: Андрей Ковальчук

Примеры реализации сортировки перемешиванием

Pascal

k:= 25; {Индекс последнего изменения}
s:= 1; {Первый элемент массива}
e:= 25; {Последний элемент массива}
while e > s do
begin
   for i:= e downto s+1 do if Arr[i] < Arr[i-1] then
   begin
      tmp := Arr[i];
      Arr[i] := Arr[i-1];
      Arr[i-1] := tmp;
      k := i;
   end;
   s:=k;
   for i:= s to e-1 do if Arr[i]>Arr[i+1] then
   begin
      tmp := Arr[i];
      Arr[i] := Arr[i+1];
      Arr[i+1] := tmp;
      k := i;
   end;
   e:=k;   
end;

Для варианта С++ и С пример не совсем соответствуют.

C++
  #include <algorithm>
 
  template< typename Iterator >
  void cocktail_sort( Iterator first, Iterator last )
  {
      for( --last; first < last; --last, ++first )
      {
          for( Iterator i = first; i < last; ++i )
              if ( *(i + 1) < *i )
                  std::iter_swap( i, i + 1 );
 
          for( Iterator i = last - 1; i > first; --i )
              if ( *i < *(i - 1) )
                  std::iter_swap( i, i - 1 );
      }
  }

C
#define SWAP(A,B) {(A)=(A)^(B); (B)=(A)^(B); (A)=(A)^(B);}
 
void m_sheker(int mas[], int n)
{
        int last = n-1, left = 1, right = n-1, j;
 
        do
        {
                for(j = right; j >= left; j--)
                {
                        if(mas[j-1] > mas[j])
                        {
                                SWAP(mas[j-1], mas[j]);
                                last = j;
                        }
                }
 
                left = last + 1;
 
                for(j = left; j <= right; j++)
                {
                        if(mas[j-1] > mas[j])
                        {
                                SWAP(mas[j-1], mas[j]);
                                last = j;
                        }
                }
 
                right = last-1;
 
        } while(left < right);
}

C#
 public static void ArrSort(int[] name)
        {
            int b = 0;
            int left = 0;//Левая граница
            int right = name.Length - 1;//Правая граница
            while(left<right) 
            { 
                for (int i = left; i < right; i++)//Слева направо...
                {
                   if (name[i] > name[i + 1])
                        {
                            b = name[i];
                            name[i] = name[i + 1];
                            name[i + 1] = b;
                            b= i;
                        }
                }
                right = b;//Сохраним последнюю перестановку как границу
                if (left >= right) break;//Если границы сошлись выходим
                for (int i = right; i > left; i--)//Справа налево...
                {
                   if (name[i-1] > name[i])
                        {
                            b = name[i];
                            name[i] = name[i-1];
                            name[i -1] = b;
                            b = i;
                        }
                }
                left = b;//Сохраним последнюю перестановку как границу
            }
        }

Fortran
program cocktailsort
 
integer A(17)
integer i,t
logical::sort=.true.
open(1,file='massiv.txt',status='old')
        read(1,*) A
                do i=1,17
                        write(*,*) A(i)
                enddo
do while(sort)
sort=.false.
        do i=1, 16
                if(A(i)>A(i+1)) then
                        t=A(i)
                        A(i)=A(i+1)
                        A(i+1)=t
                        sort=.true.
                endif
        enddo
sort=.false.
 
        do i=16, 1, -1
                if(A(i)>A(i+1)) then
                        t=A(i)
                        A(i)=A(i+1)
                        A(i+1)=t
                        sort=.true.
                endif
        enddo
enddo
write(*,*) '---'
do i=1,17
        write(*,*) A(i)
enddo
pause
end

Perl
while ( $left < $right ) { 
        for ( my $j = $right; $j >= $left; $j-- ) { 
                if ( $array_for_sort[$j-1] > $array_for_sort[$j] ) { 
                        ( $array_for_sort[$j-1],$array_for_sort[$j]) = ( $array_for_sort[$j],$array_for_sort[$j-1] );
                        $last = $j;
                }
        }
        $left = $last + 1;
        for( my $j = $left; $j <= $right; $j++ ) {
                if ( $array_for_sort[$j-1] > $array_for_sort[$j] ) { 
                        ( $array_for_sort[$j-1],$array_for_sort[$j] ) = ( $array_for_sort[$j],$array_for_sort[$j-1] );
                        $last = $j;
                }
        }  
        $right = $last - 1;
}

Добавлено: 09 Мая 2018 17:55:46 Добавил: Андрей Ковальчук

Калькулятор взвешенных оценок

В этот раз речь пойдет о создании калькулятора для расчета взвешенных оценок. Такие оценки часто используют при проведении различных тестирований и сравнений.

Например, вы хотите сравнить несколько мобильных телефонов между собой. Выбираете параметры, которые для вас важны (пусть это будут: цена, размер дисплея и вес) и для каждого из них выставляете оценку.

Естественно некоторые параметры будут важнее чем другие. Например, цена важнее веса. И вы хотите это учесть.

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

В суммарную оценку входит сумма оценок всех параметров, умноженных на их вес.

При этом удобно, чтобы сумма весов всех параметров равнялась 1 (100%). Например, цена – 50%, размер дисплея – 40%, вес – 10%.

Теперь рассмотрим пример создания такого калькулятора для 3-х параметров.

Нам понадобятся 3 поля для ввода оценок каждого из параметров и 3 слайдера (slider) для задания их весов.

В данном случае слайдеры создадут очень наглядное представление весов параметров. К тому же мы сделаем их связанными между собой и пользователю не придется следить за тем, чтобы сумма их значений была равна 100%.

Сразу хочу обратить ваше внимание на чекбоксы (checkbox) справа от слайдеров. Они служат для того, чтобы заблокировать изменение соответствующего слайдера. Т.к. слайдеров у нас три, то при перемещении одного из них, будут изменяться значения остальных.

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

Структура и принцип работы калькулятора

Наше приложение состоит из одной HTML страницы, трёх JavaScript файлов (из них два – это библиотеки jQuery и jQuery UI) и 2-х файлов с CSS стилями.

Начнём со страницы – index.html.

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
 
<head>
  <title>Каклькулятор, взвешенные оценки</title>
 
  <meta http-equiv="content-type" content="text/html;charset=utf-8" />
  <meta http-equiv="Content-Style-Type" content="text/css" />
 
  <meta name="description" content="Использование ползунков (slider) для создания калькулятора" />
  <meta name="keywords" content="калькулятор, ползунки, slider, взвешенная оценка" />
  
  <link rel="stylesheet" type="text/css" href="css/ui-lightness/jquery-ui-1.7.2.custom.css" media="all" />
  <link rel="stylesheet" type="text/css" href="styles.css" media="all" />
</head>
 
<body>
 
<div id="parameter_1" class="calc_row">
  <input type="text" name="val_1" id="val_1" class="val_field" value="0" />
  <div id="weight_1" class="slider"></div>
  <div id="sv_1" class="slider_val"></div>
  <input type="checkbox" class="sl_enable" />
</div>
 
<div id="parameter_2" class="calc_row">
  <input type="text" name="val_2" id="val_2" class="val_field" value="0" />
  <div id="weight_2" class="slider"></div>
  <div id="sv_2" class="slider_val"></div>
  <input type="checkbox" class="sl_enable" />
</div>
 
<div id="parameter_3" class="calc_row">
  <input type="text" name="val_3" id="val_3" class="val_field" value="0" />
  <div id="weight_3" class="slider"></div>
  <div id="sv_3" class="slider_val"></div>
  <input type="checkbox" class="sl_enable" />
</div>
 
<div id="results"></div>
 
<script type="text/javascript" src="js/jquery-1.3.2.min.js"></script>
<script type="text/javascript" src="js/jquery-ui-1.7.2.custom.min.js"></script>
<script type="text/javascript" src="js/main.js"></script>
</body>
</html>


В заголовке страницы мы подключили CSS файлы (строки 15 и 16). Первый распространяется вместе с jQuery UI и используется для оформления слайдеров, второй – используется для оформления страницы.

Сама страница содержит три практически одинаковых блока. В каждый из них входят:

— текстовое поле — задаёт оценку параметра;
— слайдер – указывает вес параметра;
— текстовая надпись – отображает текущее значение слайдера;
— чекбокс (checkbox) – используется для включения/отключения слайдера.

За ними расположен блок, показывающий суммарную оценку (строка 42)

В конце страницы мы подключаем JavaScript файлы (строки 44-46). Сначала библиотека jQuery, затем jQuery UI и файл с нашими скриптами (main.js).

Теперь рассмотрим наш main.js. Это самая сложная и объёмная часть калькулятора. Но большая часть кода касается настройки взаимной работы слайдеров и чекбоксов.


$(function() {
  /* создаем слайдеры */
  $(".slider").slider();
  
  /* устанавливаем начальные значения */
  $(".sl_enable").attr('checked', false);
 
  $(".slider").each(function() {
    $(this).slider('option', 'value', 33.3);
  });
  
  $(".slider_val").html("33.3 %");
  
  $('.val_field').val('0');
  
  calculate();
  
  /* минимальное и максимальное значение активных слайдеров */
  var min = 0;
  var max = 100;
  
  /*
  Устанавливаем обработчики чекбоксов.
  Использовать событие change не получается, т.к. в IE оно возникает
  после того как checkbox теряет фокус (т.е. после переключения
  checkbox'а нужно кликнуть где-нибудь на странице, чтобы возникло
  событие change)
  */
  $(".sl_enable").click(function() {
    var curId = getCurId(this);
    var curSlider = $('#weight_' + curId);
    if (this.checked) {
      curSlider.slider('disable');
      $("#sv_" + curId).addClass('gray');
    }
    else {
      curSlider.slider('enable');
      $("#sv_" + curId).removeClass('gray');
    }
    setMinMax();
  });
  
  /* обработчик событий slide слайдеров (возникает при перемещении слайдера) */
  $(".slider").bind('slide', function(event, ui) {
    //блокируем перемещение слайдера если оно выходит за допустимые пределы
    if ((ui.value > max) || (ui.value < min)) {
      return false;
    }
    updateSliders(this, ui.value);
    updateLabels();
    calculate();
  })
  .bind('slidestop', function() {
    /*
    Этот обработчик вызывается после перемещения слайдера.
    Нужен для того, чтобы обновить значение текущего слайдера
    (событие slide возникает раньше)
    */
    calculate();
    updateLabels();
  });
  
  /* Эта функция возвращает id текущего слайдера */
  function getCurId(elem) {
    var parentId = $(elem).parent().attr('id');
    return parentId.substring(10);
  }
  
  /*
  Эта функция устанавливает минимально и максимально допустимые значения
  слайдеров.
  */
  function setMinMax() {
    var enabledSliders = $(".slider[aria-disabled!=true]");
    var disabledSliders = $(".slider[aria-disabled=true]");
    
    // определяем сумму значений, установленных на отключенных слайдерах
    var total = 0;
    disabledSliders.each(function() {
      total += $(this).slider('option', 'value');
    });
    
    // задаём минимальные и максимальные значения для включенных слайдеров
    max = 100 - total;
    min = 0;
    if (enabledSliders.length == 1) {
      min = max;
    }
  }
  
  /*
  Изменяет положение слайдеров так чтобы сумма их значений всегда была
  равна 100
  */
  function updateSliders(curSlider, curVal) {
    var enabledSliders = $(".slider[aria-disabled!=true]");
    if (enabledSliders.length == 1) {
      return;
    }
    var newVal = (max - curVal) / (enabledSliders.length - 1);
    enabledSliders.each(function(i, slider) {
      if (slider != curSlider) {
        $(slider).slider('option', 'value', newVal);
      }
    });
  }
  
  /* Обновляет надписи с текущими значениями слайдеров */
  function updateLabels() {
    for (var i = 1; i <= 3; i++) {
      var curVal = $("#weight_" + i).slider('option', 'value');
      //округляем до десятых
      curVal = Math.round(curVal*10) / 10;
      $("#sv_" + i).html(curVal + " %");
    }
  }
  
  /* проверка значений, введенных в текстовое поле */
  
  var textFieldVal;
  
  $('.val_field').bind('keydown', function(e) {
    //сохраняем текущее значение
    textFieldVal = $(this).val();
  })
  .bind('keyup', function(e) {
    if (isNaN($(this).val())) {
      $(this).val(textFieldVal);
    }
    calculate();
  });
  
  /* Рассчет взвешенной оценки */
  function calculate() {
    var res = 0;
    
    for (var i = 1; i <= 3; i++) {
      res += $('#val_' + i).val() * $('#weight_' + i).slider('option', 'value') / 100;
    }
    
    //Округляем до сотых
    res = Math.round(res*100) / 100;
    
    $('#results').html('Взвешенная оценка = ' + res);
  }
});


Разберем код, начиная с функции calculate (строки 134-145), которая выполняет расчет суммарной оценки.

Здесь мы в цикле проходим по всем полям с оценками и слайдерам. Умножаем оценку на значение, установленное на слайдере и подсчитываем общую сумму.

После этого, показываем результат пользователю.

Возвращаемся в начало файла.

Прежде всего, мы создаём слайдеры (строка 3) и устанавливаем начальные значения (строки 6-14). Все оценки ставим равными 0, а веса параметров – 33,3% (100/3).

После этого, мы устанавливаем обработчики события click для чекбоксов. При включении чекбокса мы должны сделать соответствующий слайдер неактивным (строка 33) и пересчитать максимальные и минимальные значения для остальных слайдеров. Для этого используется функция setMinMax().

Рассмотрим её подробнее (строки 73-89).

Сначала мы находим все активные и отключенные слайдеры (строки 74 и 75).

Затем, рассчитываем сумму значений отключенных слайдеров и отнимаем её от 100. Полученное значение является максимально допустимым для оставшихся слайдеров.

Если у нас остался только один активный слайдер, то очевидно, что он может принять только одно значение (иначе сумма не будет равна 100). Поэтому мы присваиваем min = max.

Переходим к обработке перемещений слайдера (событие slide, строки 44-61). Точнее мы обрабатываем 2 события: slide и slidestop. Дело в том, что при возникновении события slide окончательное значение на слайдере ещё не установлено, поэтому если не обрабатывать slidestop, то в результате получим оценку для предыдущего положения слайдера.

При возникновении события slide мы проверяем не выходит ли слайдер за допустимые пределы и если да – блокируем его (строки 46-48).

После этого, мы обновляем положение остальных слайдеров (с помощь функции updateSliders), обновляем текстовые надписи и пересчитываем результат (строки 49-51).

Теперь рассмотрим функцию updateSliders (строки 95-106). Именно она устанавливает значения слайдеров так, чтобы их сумма всегда была равна 100%.

В её параметрах мы передаём указатель на текущий слайдер (его изменять нельзя) и его значение.

Принцип расчета значений остальных слайдеров такой.

Если у нас есть только один активных слайдер – не делаем ничего, т.к. он перемещаться не может.

Если есть хотя бы один активный слайдер (кроме текущего), то рассчитываем сколько нужно прибавить к значению текущего слайдера чтобы получить максимальное значение и делим результат на количество слайдеров (строка 100).

Т.е. если у нас активны все слайдеры, и на первом мы установили значение 70, то значения второго и третьего будут равны 15.

После этого, мы обновляем значения слайдеров (строка 103).

Теперь слайдеры работают так как нужно. Нам остаётся добавить проверку оценок, введённых в текстовые поля (строки 120-131).

Для этого установим обработчики событий keydown и keyup для этих полей. Принцип работы следующий.

При возникновении события keydown изменение содержимого поля ещё не произошло и мы сохраняем предыдущее значение.

А при возникновении keyup поле содержит новое значение. С помощью функции isNaN мы проверяем, является ли новое значение числом и если нет – возвращаем предыдущее.

Тут же мы пересчитываем суммарную оценку.

Заключение

Как видите, ничего сверхсложного. Самое главное при разработке таких приложений – правильно выбирать обработчики событий и следить за тем, какие данные в них доступны. Иначе можно получить очень интересные эффекты :)

Описывать подробно CSS стили я не буду. Т.к. изменение оформления слайдеров – это отдельная тема, а стили калькулятора – простые до предела.

Добавлено: 22 Апреля 2018 08:40:25 Добавил: Андрей Ковальчук

Быстрая проверка натурального числа на простоту

C++

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

Код C++

int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}


В данном алгоритме из множества отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества , которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

Код C++
int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}


Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

Код C++
int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}


Вот такие интересные наработки получились.

Добавлено: 14 Апреля 2018 07:03:40 Добавил: Андрей Ковальчук

Перенаправление stdout в область памяти (или файл)

C++

Для перенаправления stdout в область памяти (или файл) необходимо написать небольшую конструкцию.

Редирект в память или строку (std::string)

// make stdout buffer
char buf[16384]={0};
int fdpipe[2];
// make pipe
_pipe( fdpipe, sizeof(buf), O_BINARY );
// backup stdout handle
int old=_dup(_fileno(stdout));
// replace stdout handle with write-pipe
_dup2(fdpipe[1], _fileno(stdout));

// test output
fprint(stdout,"test");

// get collected buffer
int r = read(fdpipe[0],buf,sizeof(buf));
buf[r]=0;
// restore original stdout
_dup2(old, _fileno(stdout));
// make string
std::string str(buf);

Пример для работы с STL std::cout
std:stringstream oss;
std::cout.rdbuf( oss.rdbuf() );
std::cout << "here's some text";

Пример редиректа в файл
stream = freopen( "freopen.out", "w", stderr );
fprintf( stdout, "successfully reassigned\n" );
fclose( stream );

Добавлено: 11 Апреля 2018 10:48:37 Добавил: Андрей Ковальчук

Реализация метода Флойда на C++, с подробным выводом решений.

C++

Дан текст, который пользователь должен ввести в программу, найти наибольшее количество идущих подряд букв. Реализовать следующие возможности в программе:

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

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

Я думаю многим будет полезно дабы не мучать свои мозги. Программа выводит все промежуточные таблицы, а так же результат, то есть ответ. Написано без оболочки, так как до билдера мы ещё не добрались. В общем кому нужно разбираем icon smile Реализация метода Флойда на C++, с подробным выводом решений.

Буду рад если кому то это всё же понадобится. В программе за бесконечность принято вводить число «-1″ так как отрицательные веса редко встретишь. Далее всё поймёте. Если потребуется могу прокомментировать каждую строку, и как всё работает.

#include <iostream .h>

void main(){
cout< <"ALGORITM FLOIDA. NAHOZHDENIE KRATCHAISHEGO RASSTOYANIYA MEZHDU VSEMI VERSHINAMI GRAPHA."<<endl;
//cout<<"source by www.linkfight.ru"<<endl<<endl;
cout<<"vvedite razmernost' massiva: "<<endl;
int n;
cin>>n;
int arr[255][255];
 
for (int i=1; i< =n; i++){
for (int q=1; q<=n; q++){
cout<<"vvedite element a["<<i<<"]["<<q<<"]: ";
cin>>arr[i][q];
}
}
cout< <endl;
cout<<endl;
 
cout<<"isxodnaya matricca: "<<endl;
for (i=1; i<=n; i++){
for (int q=1; q<=n; q++){
cout<<arr[i][q]<<"         ";
}
cout<<endl;
}
 
cout <<endl;
cout <<endl;
cout <<endl;
cout <<endl;
 
cout<<"reshene: "<<endl;
for (int r=1; r<=n; r++){
 
	if(r==n) {
		cout <<endl;
		cout <<endl;
		cout <<"otvet: "<<endl;
	}
 
 
 
// øàãè
for (i=1; i<=n; i++){
for (int q=1; q<=n; q++){
 
 
 
if(arr[i][q]==-1 && arr[i][r]!=-1 && arr[r][q]!=-1){
arr[i][q]=arr[i][r]+arr[r][q];
} else if(arr[i][q]>arr[i][r]+arr[r][q]){
arr[i][q]=arr[i][r]+arr[r][q];
}
 
 
if(arr[i][q]&lt;0){
	cout< <"~         ";
}
else {
cout<<arr[i][q]<<"         ";
}
 
 
}
cout<<endl;
}
 
 
 
cout<<endl;
cout<<endl;
cout<<endl;
}
 
 
//cout <<"www.linkfight.ru"<<endl<<endl;
}

Буду рад вашим комментариям.

Добавлено: 11 Апреля 2018 10:46:45 Добавил: Андрей Ковальчук

Самое короткое слово в строке

C++

Организовать ввод строки, каждое слово в строке отделяется от других слов пробелами, их может быть неограниченное количество. Найти самое короткое слово в строке.
Определить символ пробела в строке можно с помощью функции isspace. Чтобы определить длину слова, воспользуйтесь функцией strlen.

#include <iostream>
#include <sstream>
#include <string>
 
int main()
{
    std::string s;
 
    std::cout << "Enter string: ";
    std::getline(std::cin, s);
 
    std::stringstream ss(s);
    std::string word(s);
 
    while (ss >> s)
          if (s.size() < word.size())
           word = s;
 
    std::cout << "Res: " << word << std::endl;
 
    return 0;
}

Результат работы программы, показан ниже:
Enter string: Прокладывай себе дорогу силой.
Res: себе

Добавлено: 11 Апреля 2018 10:42:30 Добавил: Андрей Ковальчук

Брошенное тело под углом

C++

Напишите программу , в которой по извесной начальной скорости V и времени полета тела T определяется угол aльфа под которым тело брошено по отношению к горизонту (воспользуйтесь соотношением a = arcsin(gT/2V) ).

V = 60

T = 12
Ugol = 78.5217


#include <iostream>
#include <cmath>
 
int main()
{
double V, T, param, result;
const double Pi = asin(1.0), g = 9.8;
std::cout << " V = ";
std::cin >> V;
 
std::cout<< std::endl << " T = ";
std::cin >> T;
 
 if(1 < fabs(g*T/(2*V)))
        std::cout<<"Incorrect"<< std::endl;
    else
    {
        param = asin(g*T/(2*V));
        std::cout<<"Ugol = "<<param*(90/Pi)<<std::endl;
    }
 
system("PAUSE");
return 0;
}

Добавлено: 11 Апреля 2018 10:41:07 Добавил: Андрей Ковальчук

Процедуры с числовыми параметрами

C++

Описать функцию аddRightDigit(d, k), которая должна добавлять к целому положительному числу К справа цифру D (D — целочисленное значение в диапазоне 0-9, К — целочисленное значение, которое является одновременно входным параметром и модифицируемым значением).
С помощью этой функции добавить к данному числу К цифры D1 и D2, выводя результат каждого добавления.

#include <iostream>
using namespace std;
 
void addRightDigit(int d, int & k)
{
    k=10*k+d;
}
 
int main()
{
    setlocale(LC_ALL, "rus");
    int k, d;
    cout<<"  k: ";
    cin>>k;
 
    for(int i=0; i<2; i++) //    d
    {
            while(1)
            {
                    cout<<" d: "; cin>>d;
                    if(d>=0 && d<=9)
                    {
                             addRightDigit(d, k);
                             break;
                    }
                    else
                    {
                        cout<<"   !!!"<<endl;
                    }
            }// while
            cout<<"k  "<<k<<endl;
    }// for
 
//    system("pause");
    return 0;
}

Результат работы программы показан ниже:
k: 4
d: 5
k 45
d: 2
k 452

Добавлено: 11 Апреля 2018 10:39:57 Добавил: Андрей Ковальчук

Программа табулирования функции котангенса

C++

Составить программу табулирования функции программирование на С++ на интервале [a,b] с шагом h, на языке программирования С++ в среде разработки MVS2010, в консоли.
Как уже было сказано ранее, не обязательно использовать IDE, указанную в задании. Пользуйтесь той, которая удобнее вам. Для решения данной задачи вам потребуются цикл for, кстати необязательно for, можете воспользоваться любым другим. И математические функции для нахождения котангенса. Знайте, в С++ нет отдельной функции для вычисления котангенса, но его можно вычислить, воспользовавшись функциями синуса и косинуса.

// tabulation_function.cpp: определяет точку входа для консольного приложения.
 
#include "stdafx.h"
#include <iostream>
// заголовочный файл содержит прототипы математических функций
#include <cmath>
// заголовочный файл содержит прототипы манипуляторов вывода
#include <iomanip>
using namespace std;
 
int main(int argc, char* argv[])
{
    float h = 0.1, // шаг табулирования
          a = 5.0 / 100, // левая граница интервала
          b = a + 0.5; // правая граница интервала
    cout << "y = ";
    for ( a; a <= b; a+=0.1) // цикл табулирования функции
    {
        cout << setprecision(3/*три знака после запятой*/)
             << pow(cos(log(a)) / sin(log(a)/*ctg(x)=cos(x)/sin(x)*/), 2) << "; "; // запрограммированная формула
    }
    cout << endl;
    system("pause");
    return 0;
}

Программу можно легко переделать и под другие функции, можно менять шаг табуляции, а также левую и правую границы интервала.

Добавлено: 11 Апреля 2018 10:38:34 Добавил: Андрей Ковальчук

Сумма целых чисел в строке

C++

Разработать программу, выполняющую обработку строки. Обработка строки должна осуществляться посимвольно (использование функций форматированного вывода scanf() и sscanf() не допускается). Найти сумму целых чисел, перечисленных в исходной строке через запятую. Ввод исходной строки осуществляется с клавиатуры.

Пример: 15,-2,1,0
Результат: 14


Вспоминаем как работать со строками в С++. Как-то нужно преобразовать строку к типу данных int, за вас это сделает функция atoi.

// sum_integer_string.cpp: определяет точку входа для консольного приложения.
 
#include "stdafx.h"
#include <iostream>
using namespace std;
 
int main(int argc, char* argv[])
{
    char string[100]; // строка целых чисел
    setlocale(LC_ALL, "rus");
    cout << "Введите строку чисел(числа отделяются друг от друга запятой): ";
    cin >> string;
 
    int index = 0; // индекс символа в строке
    int sum = 0;
 
    while (string[index] != '\0') //  пока не конец строки
    {
        if (string[index] != ',') // если текущий символ не запятая
        {
            sum += atoi((string + index)); // суммируем число
            while (string[index] != ',')
            index++; // увеличиваем индекс до тех пор пока не встретим запятую
        }
        else // текущий символ запятая
            index++; // инкремент индекса      
    }
 
    cout << "Сумма чисел = " << sum << endl;
    system("pause");
    return 0;
}

Обратите внимание на строку 21, функция atoi() преобразует строку в целое число. У данной функции всего один параметр — указатель на строку. То есть в качестве аргумента функции atoi() программа передаёт указатель на позицию в строке, в которой содержится цифра. И в случае, если между запятыми стоит несколько цифр, двух, трёх, четырёхразрядное число, функция atoi() захватит все разряды числа. После того как очередное число было изъято из строки с помощью оператора цикла while программа уинкрементирует индекс до тех пор пока индекс не будет указывать на символ запятой. Многократно повторяя выше описанные операции, в итоге мы получаем сумму чисел в строке.

Добавлено: 11 Апреля 2018 10:37:12 Добавил: Андрей Ковальчук

Удалить первые буквы слов

C++

Дана строка символов, которая обязательно заканчивается символом точки. Удалить из строки первые буквы каждого слова.
Примечание: написать программу с использованием стандартных функций библиотеки С++.

Enter the string and finish it with point:

Crystal Method.

So looks the input string without the first letters of each word:

rystal ethod


Ниже приведен код для этой задачи. Код самый простой и может усовершенствоваться (например разбиение его на несколько отдельных функции). В очередной раз мы благодарим Василия Шуверова за его код.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
 
int main ()
{
 
    char a[50000], s[50000];
    char b;
 
    int n=0,d=1,i,j=0;
 
    printf("Enter the string and finish it with point:\n\n");
 
    /*ввод предложения */
 
    do
    {
        b=getchar();
        a[n]=b;
        ++n;
    } while (b!= '.');
 
    --n;
 
    printf("\nSo looks the input string without the first letters of each word:\n\n");
 
    /*заполнение массива не начальными буквами каждого слова*/
 
    for (i=0;i<n;++i)
    {
 
        if (d)
        {
            a[i]=0;
            d=0;
            continue;
        }
 
        if (a[i]==' ')
        {
            d=1;
        }
 
        if (a[i] != '0')
        {
            s[j]=a[i];
            ++j;
        }
 
    }
 
        /*вывод предложения  на экран */
 
        for (i=0;i<j;++i)
        printf("%c", s[i]);
 
   return 0;
}

Добавлено: 11 Апреля 2018 10:36:04 Добавил: Андрей Ковальчук

Удалить из массива дубликаты элементов

C++

Написать функцию: int arrayUnique(int array[], int size), которая будет удалять из массива дубликаты элементов, и в конце работы вернёт новую длину массива.
Предлагаю для решения этой задачи организовать заполнение массива случайными числами. Это сократит время на ввод элементов двумерного массива.

// new_line_array.cpp: определяет точку входа для консольного приложения.
 
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
int arrayUnique(int *ar, int);
 
int main(int argc, char* argv[])
{
    srand(time(NULL));
    const int array_size = 20; // размер массива
    const int interval = 10; // масштаб генерируемых случайных чисел
    int ar[array_size];
 
    for (int counter1 = 0; counter1 < array_size; counter1++)
    {
        ar[counter1] = rand() % interval; // заполняем массив случайными числами
        cout << ar[counter1] << "  "; // печать элементов массива
    }
    cout << "\n";
 
    for (int counter1 = 0; counter1 < arrayUnique(ar, array_size)/*вызов функции отбора значений*/; counter1++)
    {
        cout << ar[counter1] << "  "; // печать элементов массива
    }
    cout << endl;
 
    system("pause");
    return 0;
}
 
int arrayUnique(int *ar, int size) // функция, определяющая элементы массива в единственном экземпляре
{
    for (int counter1 = 0; counter1 < size; counter1++)
    {
        for (int counter2 = counter1 + 1; counter2 < size ; counter2++)
        {
            if ( ar[counter1] == ar[counter2] ) // если найден одинаковый элемент
            {
                for (int counter_shift = counter2; counter_shift < size -1; counter_shift++)
                {
                    // выполнить сдвиг всех остальных элементов массива на -1, начиная со следующего элемента, после найденного дубля
                    ar[counter_shift] = ar[counter_shift + 1];
                }
                size -= 1; // уменьшить размер массива на 1
 
                if (ar[counter1] == ar[counter2]) // если следующий элемент - дубль
                {
                 counter2--; // выполнить переход на предыдущий элемент     
                }
            }
        }
    }
    return size;
}

Добавлено: 11 Апреля 2018 10:34:14 Добавил: Андрей Ковальчук

Поиск k-й цифры в строке

C++

Составить программу, которая на входе должна получать последовательность цифр, после чего программа показывает цифру, порядковый номер которой ввел пользователь.

#include <iostream>
#include <cstring> // для функции strlen
using namespace std;
 
int main()
{
    char string[100]; //символьный массив, для хранения введённой последовательности цифер
    cout << "Введите последовательность цифер: ";
    cin >> string;
 
    int k; // переменная целого типа, для хранения порядкового номера цифры
    cout << "\nВведите порядковый номер цифры: ";
    cin >> k;
    // проверка порядкового номера
    if ((k - 1) < 0 || k > strlen(string)) // если введённый пользователем порядковый номер выходит за пределы действительных порядковых номеров
        cout << "\nНекорректный ввод порядкового номера" << endl << endl; // напечатать соответствующее сообщение
    else
    cout << "\nk-я цифра последовательности: " << string[k -1] << endl; // вывод к-й цифры последовательности
    return 0;
}

Добавлено: 11 Апреля 2018 10:33:14 Добавил: Андрей Ковальчук

Определить количество новых строк в тексте

C++

Дан текст произвольной длины оканчивающийся символом '#'. Определить количество строк в тесте, каждая строка заканчивается символом перевода строки '\n'.

#include <iostream>
 
using namespace std;
 
int main()
{
    char text[] = "последовательная обработка\n символов\nстроки в С++\nпрограммирование на С++\nколичество строк#";
    int counter = 0, // индекс символов
        new_string = 0; // счётчик строк
 
    while (text[counter] != '#') // посимвольная обработка текста
    {
        if (text[counter] == '\n')
            new_string++; // инкремент счётчика строк
        counter++; // инкремент индекса символов
    }
 
    cout << "Количество новых строк = " << new_string << endl;
 
    return 0;
}

Добавлено: 11 Апреля 2018 10:32:16 Добавил: Андрей Ковальчук