понедельник, 14 февраля 2011 г.

Операторы цикла

Цикл For. Блок 2. Задачи на цикл For.

Задача A. Четные числа
Выведите (через пробел) все четные числа от a до b (включительно).

  1. int a, b ;
  2. cin >> a >> b;
  3.  
  4. for (int i = a; i <= b; i++)
  5.   if (i % 2 == 0)
  6.     cout << i << ' ';
* This source code was highlighted with Source Code Highlighter.


Задача B. Остаток
Вводятся 4 числа: a, b, c и d.
Выведите все числа на отрезке от a до b, дающие остаток c при делении на d.

  1.   int a, b, c, d ;
  2.   cin >> a >> b >> c >> d;
  4.   for (int i = a ; i <= b ; i++)
  5.     if (i % d == c)
  6.       cout << i << ' ';
* This source code was highlighted with Source Code Highlighter.


Задача C. Квадраты
Выведите все числа на отрезке от a до b, являющиеся полными квадратами.

Вариант 1.

  1.   int a , b;
  2.   cin >> a >> b ;
  4.   int sqrt_a = ceil(sqrt(a + 0.0));
  5.   int sqrt_b = sqrt((double)b);
  6.   for (int i = sqrt_a ; i <= sqrt_b ; i++)
  7.       cout << i*i << " ";

* This source code was highlighted with Source Code Highlighter.

В этом случае мы рационально движемся от sqrt(a) к sqrt(b), т.к. проверка меньших и больших значений смысла не имеет.
Нужно обратить внимание, что корень от а округляется в большую сторону ceil(sqrt(a + 0.0) перед отправкой в цикл: если а – и есть полный квадрат, то это число также должно быть выведено, однако, если а дает дробный корень, то его целая часть (при приведении к типу int) даст заведомо меньший квадрат, чем значение а. Поэтому мы заранее округляем sqrt(a) до следующего целого числа, дабы избежать выведение лишнего квадрата.

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

  1.  int a,b;
  2.   cin>>a>>b;
  3.   for (int i=a;i<=b;i++)
  4.   {
  5.     int Sqrt = sqrt((double)i);
  6.     if ( Sqrt*Sqrt == i)
  7.       cout<<i<<' ';
  8.   }
* This source code was highlighted with Source Code Highlighter.


Задача H. Делители числа
Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

  1.   int x;
  2.   cin >> x;
  3.  
  4.   for (int i = 1 ; i <= x ; i++)
  5.     if ( x % i == 0 )
  6.       cout << i << ' ';
* This source code was highlighted with Source Code Highlighter.


Задача I. Количество делителей
Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x <= 30000).

  1.   int x, k = 0;
  2.   cin >> x;
  3.  
  4.   for (int i = 1; i <= x; i++)
  5.     if (x % i == 0 )
  6.       k++;
  7.   cout << k;
* This source code was highlighted with Source Code Highlighter.


Задача J. Сумма ста
Вычислите сумму данных 100 натуральных чисел. Вводятся 100 чисел, сумму которых необходимо посчитать.

  1.   int x;
  2.   long long sum = 0;
  3.  
  4.   for (int i = 1; i <= 100; i++)
  5.   {
  6.     cin >> x;
  7.     sum += x;
  8.   }
  9.   cout << sum ;
* This source code was highlighted with Source Code Highlighter.


Задача K. Сумма чисел
Вычислите сумму данных N натуральных чисел. Вводится число N, а затем N чисел, сумму которых необходимо вычислить.

  1.   int n, x;
  2.   long long sum = 0;
  3.   cin >> n;
  4.  
  5.   for (int i = 1; i <= n; i++)
  6.   {
  7.     cin >> x;
  8.     sum += x;
  9.   }
  10.   cout << sum ;
* This source code was highlighted with Source Code Highlighter.


Задача M. Нули
Вводится число N, а затем N чисел. Подсчитайте, сколько среди данных N чисел нулей.

  1.   int n , x , k = 0;
  2.   cin >> n;
  3.  
  4.   for (int i = 1; i <= n ; i++)
  5.   {
  6.     cin >> x;
  7.     if (x == 0)
  8.       k++;
  9.   }
  10.   cout << k;
* This source code was highlighted with Source Code Highlighter.


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

Вариант 1.

  1.   int n, x;
  2.   int zero = 0, pos = 0, neg = 0;
  3.   cin >> n;
  4.  
  5.   for (int i = 1; i <= n ; i++)
  6.   {
  7.     cin >> x;
  8.     if (x == 0)   zero++;
  9.     else if (x > 0) pos++;
  10.     else      neg++;
  11.   }
  12.   cout<<zero<<' '<<pos<<' '<<neg;
* This source code was highlighted with Source Code Highlighter.

При данной реализации мы каждый раз в цикле прогоняем последовательную проверку числа на знак. Сейчас это не доставляет никаких неудобств, т.к. мы имеем всего 3 критерия подсчета. Однако, если б требовалась более широкая проверка, например, относительно 10-ти различных случаев, то рациональнее было бы использовать сase–структуру. Что и сделано в варианте 2

Вариант 2.
Используем сase–структуру для определения знака, предварительно нормировав ненулевые значения в единицу (1/-1).

  1.   int n, x;
  2.   int zero = 0, pos = 0, neg = 0;
  3.   cin >> n;
  4.  
  5.   for (int i = 1; i <= n ; i++)
  6.   {
  7.     cin >> x;
  8.    
  9.     if (x)
  10.       x /= abs(x);
  11.     switch(x)
  12.     {
  13.     case 1: pos++; break;
  14.     case 0: zero++; break;
  15.     case -1: neg++; break;
  16.     }
  17.   }
  18.   cout<<zero<<' '<<pos<<' '<<neg;
* This source code was highlighted with Source Code Highlighter.


Задача O. Ноль или не ноль
Проверьте, есть ли среди данных N чисел нули. Вводится число N, а затем N чисел. Выведите YES, если среди введенных чисел есть хотя бы один нуль, или NO в противном случае.

Вариант 1.

  1.   int x, n;
  2.   cin >> n;
  3.   bool zeroExist = false;
  4.  
  5.   for (int i = 1; i <= n ; i++)
  6.   {
  7.     cin >> x;
  8.     if (x == 0)
  9.     {
  10.       zeroExist = true;
  11.       break;
  12.     }
  13.   }
  14.   if (zeroExist)
  15.     cout<<"YES";
  16.   else
  17.     cout << "NO";

This source code was highlighted with Source Code Highlighter.


Вариант 2.
Ту же самую идею можно описать короче.

  1.   int x, n;
  2.   cin >> n;
  3.   bool zeroExist = false;
  4.  
  5.   for (int i = 1; i <= n ; i++)
  6.   {
  7.     cin >> x;
  8.     zeroExist = zeroExist | (x == 0);
  9.     if (zeroExist)
  10.       break;
  11.   }
  12.   cout<<(zeroExist ? "YES" : "NO");
* This source code was highlighted with Source Code Highlighter.


Задача P. Уравнение по возрастанию
Вводятся 4 числа: a, b, c и d.
Найдите все целые решения уравнения ax3 + bx2 + cx + d = 0 на отрезке [0,1000] и выведите их в порядке возрастания.

  1.   long long a , b , c , d ;
  2.   cin >> a >> b >> c >> d;
  3.  
  4.   for (int i = 0; i <= 1000 ; i++)
  5.     if ( a*i*i*i + b*i*i + c*i + d == 0)
  6.       cout<< i <<' ';
* This source code was highlighted with Source Code Highlighter.


Задача Q. Уравнение по убыванию
Вводятся 4 числа: a, b, c и d.
Найдите все целые решения уравнения ax3 + bx2 + cx + d = 0 на отрезке [0,1000] и выведите их в порядке убывания.

  1.   long long a, b, c, d;
  2.   cin >> a >> b >> c >> d;
  3.  
  4.   for (int i = 1000; i >= 0; i--)
  5.     if (a*i*i*i + b*i*i + c*i + d == 0)
  6.       cout << i <<' ';
* This source code was highlighted with Source Code Highlighter.


Задача R. Количество решений
Вводятся 5 чисел: a, b, c, d и e.
Найдите все целые решения уравнения ( ax3 + bx2 + cx + d ) / ( x - e ) = 0 на отрезке [0,1000] и выведите их количество.

  1.   long long a, b, c, d, e;
  2.   cin >> a >> b >> c >> d >> e ;
  3.   int k = 0;
  4.  
  5.   for (int i = 0; i <= 1000; i++ )
  6.     if (a*i*i*i + b*i*i + c*i + d == 0)
  7.       if (i - e != 0)
  8.         k++;
  9.   cout << k ;
* This source code was highlighted with Source Code Highlighter.


Задача S. ГНЧЭ-1
"ГНЧЭ-1"  – сложное электронное устройство, выдающее каждую секунду очередное число последовательности 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5... Ввиду дороговизны электронных комплектующих вам поручено разработать эмулятор для этого устройства. 
Дано количество секунд (от 1 до 1000000), которые работает генератор после включения. Вывести результат работы генератора

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

  1.   int n;
  2.   cin >> n;
  3.   int cur = 1 , count = 0;
  4.  
  5.   for (int i = 1; i <= n; i++)
  6.   {
  7.     cout<< cur <<' ';
  8.     count++;
  9.     if (cur == count)
  10.     {
  11.       cur++;
  12.       count = 0;   
  13.     }
  14.   }
* This source code was highlighted with Source Code Highlighter.

Вариант 2. 
В этом варианте решения идея та же. Однако контроль за количеством отработанных секунд и количеством напечатанных текущих значений возложены на два отдельных цикла. 
Итак, здесь мы ведем подсчет напечатанных позиций pos , которых должно быть ровно столько же, сколько секунд работает машина. А внутренним циклом задаем печать текущего числа cur . Проверка условия   if (pos == n) не даст задержаться во внутреннем цикле дольше положенных секунд.

  1.   int n;
  2.   cin >> n;
  3.   int pos = 0, cur = 1;
  4.  
  5.   for ( ; pos < n ; )
  6.   {
  7.     for (int i = 0; i < cur; i++)
  8.     {
  9.       printf("%d ", cur);
  10.       pos++;
  11.       if (pos == n)
  12.         break;
  13.     }
  14.     cur++;
  15.   }
* This source code was highlighted with Source Code Highlighter.
Автор: на

3 комментария:

Подписаться на: Комментарии к сообщению (Atom)