среда, 25 сентября 2013 г.

с++ / Задача Иосифа Флавия

Задача Иосифа (циклический список)

Описание задачи:
http://ru.wikipedia.org/wiki/Задача Иосифа


Решение (Перебором от http://cppalgorithms.blogspot.ru ) :


#include <iostream>
using namespace std;

class Node   //Узел связного списка
{
public:
int m_item;
Node *m_next;

Node(int item, Node *next){m_item = item, m_next = next;}
};

int main()
{
cout << "Enter number of people: ";
int numberOfPeople = 0;
cin >> numberOfPeople;

cout << "Enter interval: ";
int interval;
cin >> interval;

Node *first =new Node(1, 0); //Создаем первый узел. m_item содержит номер
first->m_next = first;       //и зацикливаем его на себя

Node *tmp = first;  //Указатель с которым будем работать в дальнейшем

for (int i = 2; i <= numberOfPeople; ++i)  //Создаем циклический список
{
tmp->m_next = new Node(i, first);
tmp = tmp->m_next;
}
while (tmp != tmp->m_next)    //Удаляем элемент через интервал
{
for (int i = 1; i < interval; ++i)
{
tmp = tmp->m_next;
}
Node *deleteNode = tmp->m_next;
tmp->m_next = tmp->m_next->m_next;

delete deleteNode;
}

cout << tmp->m_item << endl;  //Выводим оставшийся
}

/////////////////////////////////////////////////
Простая рекурсивная реализация (в 1-индексации):
int joseph (int n, int k) {
 return n>1 ? (joseph (n-1, k) + k - 1) % n + 1 : 1;
}
Нерекурсивная форма:
int joseph (int n, int k) {
 int res = 0;
 for (int i=1; i<=n; ++i)
  res = (res + k) % i;
 return res + 1;
}

с++ / Остатки

Остатки. Задумано целое число Х. Известны числа k, m, n – остатки от деления этого числа на 3, 5, 7 соответственно. Найдите число Х.

#include <iostream>
using namespace std;
int main()
{
int k,m,n,p;
cin>>k>>m>>n;
cout<<"interval";
cin>>p;
for(int x=0; x<p; x++) 
{
  if ((x%3)==k && (x%5)==m && (x%7)==n)
  {
    cout<<x<<endl;
  }
}

return 0;
}

c++ / диагональ прямоугольника

//Прямоугольник, стороны которого выражены натуральными числами M и N ,
//разделен на квадраты размером 1 x 1. Найти число квадратов, пересекаемых диагональю
//прямоугольника (пересекает только тогда, когда делит его на две произвольные части).

#include <iostream>
using namespace std;
int  euclid(int  A, int  B)
{
   // return B ? euclid(B, A % B) : A;
if (B)
  return euclid(B, A % B);
else
  return A;
}

int  chislo_kvad(int A, int B )
{
    return A + B - euclid(A, B);
}

int main()
{
    std::locale::global(std::locale(""));
    std::cout << "стороны прямоугольника:"
              << std::endl
              << '\t'
              << "A = ";

    int  A = 0;
    std::cin >> A;
    std::cout << '\t'
              << "B = ";
    int  B = 0;
    std::cin >> B;

    std::cout
              << chislo_kvad(A, B)
              << " квадратов."
              << std::endl;
}*/

с++ / последовательность 1 22 333 4444

Вычислить n-ый член последовательности натуральных чисел 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, … по заданному n.
#include <iostream>
using namespace std;
int main()
{
int a,b,k;
cin>>a;
if(a<1)
{
cout<<"FALSE";
}
else
{
k=1;
b=0;
while(b<a)
{
b=b+k;
k++;
}
cout<<k-1<<endl;
}

return 0;
}

с++ / текст (от n до m)

Дан текстовый файл, содержащий буквенные и цифровые символы. Требуется скопировать часть файла с позиции n до позиции m в поток и посчитать в этой части количество цифровых символов.

#include <fstream>
#include <iostream>
using namespace std;
int main()
{   
    ifstream ifs("1.txt");
    if(!ifs) 
    {
        cerr << "File error." << endl;
        return 1;
    }
    
    int n, m;
    do
    {
        (cin >> n >> m).get();
    } 
while (n < 0 || m < 0 || m <= n);
    ifs.seekg(n);
    int kol = 0;
    char temp;
    while(ifs.get(temp))
    {
        if(isdigit(temp))
        {
            kol++;
            cout << temp << ' ';
        }
        ++n;
        if (n == m) break; 
    }
    cout << endl << kol << endl;
    cin.get();
    return 0;
}

c++ / Колония роботов

Колония роботов живет и развивается по следующим законам: один раз в начале года они объединяются в группы по 3 или 5 роботов. За один год группа из 3 роботов собирает 5 новых роботов, а группа из 5 роботов собирает 9 новых роботов. Роботы объединяются так, чтобы собрать за год наибольшее количество новых роботов. Каждый робот живет три года после сборки. Известно, что начальное количество роботов равно k и все они только что собраны. Сколько роботов будет содержать колония через n лет?

#include <iostream>
using namespace std;

int main()

 { 
    int a;
    int c=0,b=0,d=0;
    int m=0;
cin>> a;
    int n;
cin>>n;
for(int i=1;i<n;i++)
{ d=a+b+c;
if(d<3)
d=0;
if(d==4 || d==7)
d-=1;
m=d%5;
c=b;
b=a;
a=d*2-d/5-m%3-m/3;
}
cout<<a+b+c<<endl;

return 0;
}

c++ / Лестница

.Лестница. Поднимаясь по лестнице, заяц прыгает либо на следующую ступеньку, либо через одну, либо 

#include <iostream>
using namespace std;
int main()
{
int a=1,b=2,c=4,d=0,num;
cout<<"количество ступенек =  ";
cin>>num;
if(num==1)
{
d=a;
}
if(num==2)
{
d=b;
}
if(num==3)
{
d=c;
}
if(num>3)
{
for(int i=0;i<(num-3);i++)
{
d=a+b+c;
a=b;
b=c;
c=d;
}
}
cout<<"способoFF = "<<d;
return 0;

}

c++ / Квадраты

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

#include<iostream>
using namespace std;
int main()
{
        int x, y;
cin>>x>>y;
 int count=0;
 while(x>0 && y>0)
 {
  if(x>y)
{
x -= y;
}
else
{
y -= x;
}
  count++;
 }
 cout<<count;
  return 0;
}

с++ / not(1) = 0, not (0) = 1

 Последовательность 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, …, состоящая из нулей и единиц строится так: первый ее элемент равен 1, а остальные получаются из предшествующих с помощью логической операции отрицания: not(1) = 0, not (0) = 1. Второй элемент равен отрицанию первого, третий и четвертый – отрицанию первого и второго соответственно и т.д. По заданному n вычислить n-ый член указанной последовательности.


#include <iostream>
using namespace std;
int step(int x) //Если  0 или 2^n, то --. результат не может быть 0, 1, 2, 4 и т.д.
{
    x--;
    while (!(x & (x - 1)))
        x--;
    return x;  
}

int main(void)
{
    int n;
cout<<"CHISLO : ";
    cin >> n;

    if (n == 1)
        cout << 1;
    else if (n == 2)
        cout << 0;
    else
    {
        int k = 0;
        while(n > 2)
        {
            n -= step(n);
            k++;
        }

        if (((n == 1) && (k % 2 != 0)) || ((n == 2) && (k % 2 == 0)))
            cout << 1;
        else
            cout << 0;
    }

    return 0;  
}