Поиск
 
 

Результаты :
 


Rechercher Расширенный поиск

Кто сейчас на форуме
Сейчас посетителей на форуме: 1, из них зарегистрированных: 0, скрытых: 0 и гостей: 1

Нет

[ Посмотреть весь список ]


Больше всего посетителей (9) здесь было Вс Фев 11, 2018 12:54 pm
Самые активные пользователи за неделю
Ярослав
 


Дополнительные задания.

Перейти вниз

Дополнительные задания.

Сообщение автор Дмитрий в Вт Фев 07, 2017 10:18 pm

Ярослав, здравствуйте!

1. Посоветуйте, пожалуйста, какой нибудь сборник задач или ссылку на сайт, где можно встретить интересные задания.
2. Можно Вас попросить добавить 1-2 дополнительных сложных задач.

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Ср Фев 08, 2017 1:22 am

Добрый вечер!

1. Я сам не знаю таких сайтов, мне обычно задачи встречаются сами по жизни. Вот нагуглил (искал «задачи по программированию»), вроде выглядит хорошо:

http://cppstudio.com/cat/285/
(уровень сложности Easy / Normal)

http://purecodecpp.com/archives/433
Меньше задач, зато они сгруппированы по темам


Последний раз редактировалось: Ярослав (Ср Фев 08, 2017 1:39 am), всего редактировалось 1 раз(а)
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Ср Фев 08, 2017 1:33 am

2. На тему нашего последнего урока (массивы).

1) Решето Эратосфена.

Это знаменитый алгоритм, позволяющий легко и быстро строить список простых чисел. Например, хотим найти все простые числа от 1 до 4000.

Смысл такой: заводим гигантский массив, в данном случае из 4000 элементов, где каждый элемент — ответ на вопрос: является ли это число простым? (То есть булева переменная). Изначально предполагаем, что все числа простые.

Затем пробегаем по нему, вычёркивая каждое второе число. Саму двойку оставляем, но за ней каждое второе число отмечаем как не-простое (составное).
Затем пробегаем по массиву, вычёркивая каждое третье число. Тройку оставляем, а за ней каждое третье отмечаем как составное.
Идём дальше по массиву. Четвёрку пропускаем, так как она у нас уже зачёркнута — составное. На ней можно сэкономить вычисления, и ничего не делать. Просто перейти к следующему кандидату.
Пятёрка. Саму пятёрку оставляем, зато каждое пятое число после неё отмечаем как не-простое.
Шестёрка вычеркнута, пропускаем.
Семёрка. Оставляем, каждое 7-е число вычёркиваем.
И так далее.

В итоге остаётся пробежать по массиву, распечатав все НЕ вычеркнутые числа — они простые.

Усложнения:
1.1) Все простые числа складировать в другую переменную-массив, так чтобы они шли по порядку, начиная с 2:
a[0] == 2
a[1] == 3
a[2] == 5
a[3] == 7
...
Распечатывать простые числа только из этого массива, не напрямую.

1.2) Решето Эратосфена достаточно выполнять не 4000 раз, а корень квадратный из 4000 раз, это связано с разложением чисел на множители. Оптимизировать программу, так чтобы она выполнялась только корень квадратный из 4000 раз.

1.3) 4000 сделать именованной константой. Это позволит изменить объём поиска, поменяв значение константы всего в одном месте.

Использовать это изменение, чтобы найти простые числа до 5 000; до 10 000.


Последний раз редактировалось: Ярослав (Ср Фев 08, 2017 1:40 am), всего редактировалось 1 раз(а)
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Ср Фев 08, 2017 1:39 am

2) Пользователь вводит цифру от 1 до 9. Например, пользователь ввёл 4. Программно сгенерировать массив, состоящий из таких чисел:

4
44
444
4444
44444
444444
...

продолжается, пока число не станет слишком большим для типа int. И распечатать его.
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Дмитрий в Пт Фев 10, 2017 7:09 pm

Ярослав пишет:2) Пользователь вводит цифру от 1 до 9. Например, пользователь ввёл 4. Программно сгенерировать массив, состоящий из таких чисел:

4
44
444
4444
44444
444444
...

продолжается, пока число не станет слишком большим для типа int. И распечатать его.

Ярослав, начал выполнять это задание и с толкнулся с небольшими нюансами(

Код:
#include <iostream>
#include <limits.h>
using namespace std;

void main()
{
 int a[15];
 int i=0;

 cout << "Enter a number in the range from 1 to 9: ";
 cin >> a[0];
 cout << "\n\n";

 do
 {
 i++;
 a[i] = a[i - 1] * 10 + a[0];
 } while (a[i] < INT_MAX);

 for (int j = 0; j < i; j++)
 cout << a[j] << endl;

 cout << endl;
}

1. Какой размер массива выбрать, если в начале работы я не знаю сколько элементов будет использоваться?
2. Нашел константу INT_MAX которая находится в библиотеке limits.h. она показывает максимальное значение типа int, но почему то программа попадает или в вечный цикл, или если я меняю условия выхода из цикла, последние элементы выдают не понятное значение.

Логически я вроде всё написал правильно.

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Пт Фев 10, 2017 7:16 pm

1. Массив должен быть достаточно большим, чтобы в него поместились все нужные элементы. Обычно такие прикидки делают на бумажке и калькуляторе, а потом вставляют в программу.

2. Константа INT_MAX здесь действительно по месту, единственная беда, что переменная типа int никогда не может стать больше, чем INT_MAX; она либо меньше, либо равна ей.

Для того, чтобы стало больше, нам нужна переменная более вместительного типа, чем int.
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Дмитрий в Сб Фев 11, 2017 10:42 am

Ярослав, спасибоУлыбаюсь
Тип массива заменил с int на long long всё заработало.

Код:
#include <iostream>
#include <limits.h>
using namespace std;

void main()
{
 long long a[15];
 int i=0;

 cout << "Enter a number in the range from 1 to 9: ";
 cin >> a[0];
 cout << "\n\n";

 do
 {
 i++;
 a[i] = a[i - 1] * 10 + a[0];
 } while (a[i] < INT_MAX);

 for (int j = 0; j < i; j++)
 cout << a[j] << endl;

 cout << endl;
}

задание выполнено.

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Дмитрий в Сб Фев 11, 2017 1:38 pm

Код:
#include <iostream>
using namespace std;

void main()
{
 const int N = 4000;
 int a[N], b[N];
 int p, j;

 for (int i = 0; i < N;i++)
 a[i] = i + 1;

 a[0] = 0;
 for (int i = 1; i < N; i++)
 if (a[i] != 0)
 {
 p = a[i];
 for (int j = i + p;j < N; j = j + p)
 a[j] = 0;
 }

 
 j = 0;
 for (int i=0; i<N;i++)
 if (a[i] != 0)
 {
 b[j] = a[i];
 j++;
 }
 for (int i = 0; i < j;i++)
 cout << b[i] << ' ';
 cout << endl;
}

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Сб Фев 11, 2017 3:34 pm

Задание 1.2) про квадратный корень?

Если x — число, то sqrt(x) — вычисляет квадратный корень из x.

Функция sqrt() определена в <math.h>
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Сб Фев 11, 2017 3:59 pm

Двумерные массивы

7.1. Умножение матриц.

Матрица A имеет размер M строк, N столбцов.
Матрица B имеет размер N строк, P столбцов.
При их умножении получается матрица C из M строк и P столбцов.

На каждом месте находится скалярное произвдение i-й строки из A на j-й столбец из B:

c[i][j] = сумма по k a[i][k] * b[k][j]

Посчитать на компьютере умножение матриц:
Код:
   1 0 0        1 2 3
A = 0 1 0 , B = 4 5 6 ,  C = ?
    0 0 1        7 8 9

    0 1 0       1 2 3
A = 1 0 0 , B = 4 5 6 ,  C = ?
    0 0 1       7 8 9

    1 0 1       1
A = 0 1 1 , B = 2 ,  C = ?
    0 0 1       3
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Дмитрий в Вс Фев 12, 2017 9:25 pm

Ярослав пишет:Задание 1.2) про квадратный корень?


Ярослав, я немного не понимаю это задание. Я сделал некоторые изменения.
Посмотрите, пожалуйста, я правильно понял?

Если нет, то напишите что надо конкретно исправить.

Код:

#include <iostream>
#include <math.h>

using namespace std;

void main()
{
   const int N = 4000;
   int a[N], b[N];
   int p, j;

   
   for (int i = 0; i < N;i++)
      a[i] = i + 1;
   
   a[0] = 0;
   for (int i = 1; i < N; i++)
      if (a[i] != 0)
      {
         p = a[i];
         for (int j = i + p;j < sqrt(N); j = j + p)
            a[j] = 0;
      }

      
      j = 0;
      for (int i=0; i<sqrt(N);i++)
         if (a[i] != 0)
         {
            b[j] = a[i];
            j++;
         }
      for (int i = 0; i < j;i++)
         cout << b[i] << ' ';
      cout << endl;
}

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Вс Фев 12, 2017 10:00 pm

Совершенно верно! Очень доволен
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Дмитрий в Пт Фев 17, 2017 7:10 pm

Ярослав пишет:Двумерные массивы

7.1. Умножение матриц.

Ярослав, Здравствуйте!
Проверти, пожалуйста. Всё работает.

Код:

#include <iostream>
using namespace std;

void main()
{
 const int N = 3;
 const int M = 3;
 const int P = 3;
 const int K = 1;

 int a1[N][M] = { {1,0,0},
 {0,1,0},
 {0,0,1} };
 int b1[M][P] = { {1,2,3},
 {4,5,6},
 {7,8,9} };

 int a2[N][M] = { { 0,1,0 },
 { 1,0,0 },
 { 0,0,1 } };
 int b2[M][P] = { { 1,2,3 },
 { 4,5,6 },
 { 7,8,9 } };

 int a3[N][M] = { { 1,0,1 },
 { 0,1,1 },
 { 0,0,1 } };
 int b3[M][K] = { 1,2,3 };
 
 int c1[N][P], c2[N][P], c3[N][K];

 //Матрица С1 и С2
 for (int i = 0; i < N; i++)
 for (int j = 0; j < P; j++)
 {
 c1[i][j] = 0;
 c2[i][j] = 0;
 for (int k = 0; k < M; k++)
 {
 c1[i][j] += a1[i][k] * b1[k][j];
 c2[i][j] += a2[i][k] * b2[k][j];
 }
 }
 //Матрица С3
 for (int i = 0; i < N; i++)
 for (int j = 0; j < K; j++)
 {
 c3[i][j] = 0;
 for (int k = 0; k < M; k++)
 {
 c3[i][j] += a3[i][k] * b3[k][j];
 }
 }
 // Вывод матрицы на экран
 cout << "Matrix C1:\n\n";
 for (int i = 0; i < N; i++)
 {
 for (int j = 0; j < P; j++)
 cout << c1[i][j] << ' ';
 cout << endl;
 }

 cout << "\nMatrix C2:\n\n";
 for (int i = 0; i < N; i++)
 {
 for (int j = 0; j < P; j++)
 cout << c2[i][j] << ' ';
 cout << endl;
 }

 cout << "\nMatrix C3:\n\n";
 for (int i = 0; i < N; i++)
 {
 for (int j = 0; j < K; j++)
 cout << c3[i][j] << ' ';
 cout << endl;
 }
 cout << endl;
}

Дмитрий

Posts : 10
Join date : 2017-01-23

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Ярослав в Пт Фев 17, 2017 7:15 pm

Код правильный, работает правильно. Что с отступами? Очень трудно читать.
avatar
Ярослав
Admin

Posts : 500
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Дополнительные задания.

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения