БлогNot. 17 не пригодившихся задач за начало 2016 года :)

17 не пригодившихся задач за начало 2016 года :)

Очередная подборка текущих учебных задач на C/C++, все коды проверялись в Visual Studio 2010 или 2015. Если вы пришли с поисковика, для быстрого поиска нужного слова на странице используйте в браузере комбинацию клавиш Ctrl+F.

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

#include <iostream>
#define M_PI 3.1415926
using namespace std;
 
double area(double, double, double);
 
int main() {
    double s[4];
    for (int i = 0; i < 4; i++) s[i]= area(
        1.+rand()%5, //метры 1-5
        2.+rand()%6, //метры 2-7
        (60.+rand()%90) * M_PI / 180 //градусы 60-149
        );
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 4; j++) if (s[i]>s[j]) {
            double temp = s[i]; s[i] = s[j]; s[j] = temp;
        }
    for (int i = 0; i < 4; i++) 
        cout << "S=" << s[i] << " m^2" << endl;
    
    cin.sync();  cin.get(); return 0;
}
 
double area(double b, double c, double a) {
    return b*c / 2.*sin(a);
}

2. Написать функцию, которая табулирует любую указанную функцию вида float f (float) на интервале [x1,x2] для n значений (Си, а не C++).

Применяем указатель на функцию для решения задачи.

#include <stdio.h>
#include <math.h>
#define EPS 1e-9
#define M_PI 3.1415926
 
typedef float (*function) (float);
 
void tabulator(function f, float x1, float x2, int n) {
    float step = (x2 - x1) / n,x,y;
    for (x = x1; x <= x2 + EPS; x += step) {
        y=f(x);
        printf("\n%.2f\t%.2f", x, y);
    }
}
 
float f1(float x) { return sin(x); }
float f2(float x) { return cos(x); }
 
int main() {
    printf("\nTable 1");
    tabulator(f1, 0, M_PI, 10);
    printf("\nTable 2");
    tabulator(f2, 0, M_PI, 10);
    fflush(stdin); getchar(); return 0;
}

3. Проверить с помощью рекурсивной функции, верна ли гипотеза:

1/(1*2) + ... + 1/(n*(n+1)) = n/(n+1)

"Гипотеза" верна, конечно :)

#include <iostream>
#include <math.h>
using namespace std;
#define EPS 1E-9 
 /* т.к. суммы вещественные, сравнивать имеет смысл с заданной точностью */

double sum (int n) {
 if (n<1) return 0;
 else return sum(n-1)+1./(n*(n+1));
}

int main() {
 int n;
 cout << "N=";
 cin >> n;
 cout << ( fabs(sum(n) - (0.+n)/(n+1)) < EPS ? "Yes" : "No");
 cin.sync();  cin.get(); return 0;
}

4. Кролики Фибоначчи. Эта задача придумана самим Фибоначчи в 13-м веке :)

Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод? (ответ - 377 пар).

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main () {
 int m0,m1,m2;
 m2 = 2; //1-й месяц: 1 первоначальная пара, давшая приплод, и 1 родившаяся пара
 m1 = 3; //через месяц будет 3 пары: 1 первоначальная, снова давшая приплод, 1 растущая и 1 родившаяся
 for (int m=3; m<13; m++) {
  m0 = m1+m2; //формула для остальных месяцев
  m2 = m1;
  m1 = m0;
 }
 cout << m0;
 cin.sync(); cin.get(); return 0;
}

5. Для заданных двух целых чисел реализовать оператор "побитовое исключающее ИЛИ" (без участия стандартного оператора ^).

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <bitset>
using namespace std;

int xor (int a, int b) {
 int n=8*sizeof(int); //число бит
 int c=0;
 for (int i=0; i<n; i++) {
  if ((a&1<<i) && (b&1<<i) || !(a&1<<i) && !(b&1<<i)) { //1 xor 1=0, 0 xor 0=0
   c&=~(1<<i);
  }
  else {
   c|=1<<i; 
  }
 }
 return c;
}

int main () {
 int a=4321,
     b=-2345,
     c=a^b; //только для контроля
 cout << a << " xor " << b << "=" << xor(a,b) << endl;
 cout << " (" << bitset<32>(xor(a,b)) << ")" << endl;
 cout << "Control:" << c << endl;
  cout << " (" << bitset<32>(c) << ")" << endl;
 cin.sync(); cin.get(); return 0;
}

6. Сгенерировать числа, распределённые равномерно на заданном интервале [a,b].

В новых стандартах C++ есть библиотека <random> со всеми распределениями.

Стандартный подход rand()%число как раз вряд ли даст равномерное распределение из-за взятия операции "остаток от деления" %.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <random>
using namespace std;

int main() {
 const int n = 100; //количество значений
 const int a = 1;   //границы интервала
 const int b = 1000;
 //опишем генератор и массив 
 std::default_random_engine generator;
 std::uniform_int_distribution<int> distribution(a,b);
 int p[n]={};
 //заполнение и вывод
 for (int i=0; i<n; ++i) {
  p[i] = distribution(generator);
  cout << p[i] << " ";
 }

  cin.sync(); cin.get(); return 0;
}

7. Подсчитать, сколько пpошло воскpесений от начала текущего кваpтала до последнего пpаздничного дня этого кваpтала. Известна текущая дата d.m.g.

Интересный момент о "затирании" вызовом gmtime или localtime предыдущих сохранённых значений метки времени дан большим комментарием в коде.

Праздники предусмотрены только в формате "день месяца + месяц".

#include <locale.h>
#include <windows.h>

#include <iostream>
#include <ctime>

using namespace std;

struct dt { int day,month; };
#define N_HOLIDAYS 8
dt holidays[N_HOLIDAYS] = { 
 //праздники, одна строка элементов - один квартал 
 //месяцы нумеруются с 0, как в struct tm
 {1,0},{23,1},{8,2},
 {1,4},{9,4},{12,5},
 {1,8},
 {4,10}
};

//true, если дата dt относится к кварталу q (0-3)
bool inq(dt d,int q) { return d.month/3==q ? true : false; }

//вывести дату из struct tm по формату
void prn(char *hdr, struct tm *t) {
 char * wday[7] = { "Вс","Пн","Вт","Ср","Чт","Пт","Сб"};
 cout << endl << hdr << " ";
 cout.width(2); cout.fill('0');
 cout << t->tm_mday << ".";
 cout.width(2); cout.fill('0');
 cout << (t->tm_mon+1) << "." << (t->tm_year+1900) <<
  "," << wday[t->tm_wday] << "(" << (t->tm_yday+1) << "), ";
 cout.width(2); cout.fill('0'); cout << t->tm_hour << ":";
 cout.width(2); cout.fill('0'); cout << t->tm_min << ":";
 cout.width(2); cout.fill('0'); cout << t->tm_sec;
}

int main() { 
 setlocale(LC_ALL,"Rus"); SetConsoleCP(1251); SetConsoleOutputCP(1251);

 time_t t = time(NULL);
 struct tm *now =  new struct tm();
 now =  localtime(&t);
 now->tm_sec = now->tm_min = now->tm_hour = 0;
 
 struct tm start = {0};
 start.tm_hour = start.tm_min = start.tm_sec = 0;
 start.tm_mday = 1;
 start.tm_mon = (now->tm_mon/3)*3; //0 3 6 9 - начало квартала
 start.tm_year  = now->tm_year; 
 time_t time_start =mktime (&start);

 int q = start.tm_mon / 3; //номер квартала 0-3
 struct tm end = {0};
 int k=-1;
 if (q==3) k=N_HOLIDAYS-1;
 else for (int i=0; i<N_HOLIDAYS-1; i++)
  if (inq(holidays[i],q) && !inq(holidays[i+1],q)) {
   k=i; break;
  }
 end.tm_hour = end.tm_min = end.tm_sec = 0;
 end.tm_mday = holidays[k].day;
 end.tm_mon = holidays[k].month;
 end.tm_year  = now->tm_year; 
 time_t time_end = mktime (&end);
  
 struct tm *now_r = new struct tm(*now);
 /*
  Зачем копия структуры:
  "Не рекомендуется использовать функцию gmtime () в многопоточных 
  приложениях, так как данные функции использует общую структуру для сохранения 
  преобразованного времени и одновременный вызов функции из разных потоков может 
  привести к неверному результату работы."
  Но у меня и с localtime при повторном вызове, который ниже в цикле for,
  убивалась ранее сохранённая структура now!
 */
 struct tm *current = new struct tm();
 int cnt = 0;
 for (time_t ct = time_start; ct <= time_end; ct+=86400) {
  current =  localtime(&ct); //!!!
  if (current->tm_wday == 0) cnt++;
 }

 prn("Начало квартала = ",&start);  
 prn("Сейчас = ", now_r);  
 prn("Последний праздник квартала = ", &end); 
 cout << endl << "Количество воскресений = " << cnt;
 
 cin.sync(); cin.get();  return 0;
}

8. С клавиатуры вводятся натуральные числа, ввод заканчивается числом 0. Нужно вывести на экран эти числа в порядке возрастания.

Конечно, здесь подойдёт vector, автоматически умеющий увеличивать свой размер.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() { 
 vector <int> a;  
 int a0,i=0;
 do {
  cout << "a[" << (++i) << "]=";
  cin >> a0;
  if (!a0) break;
  a.push_back(a0);
 } while (true);
 
 sort(a.begin(), a.end());
 
 for (vector<int>::const_iterator it = a.begin(); it != a.end(); ++it)
   cout << *it << ' ';
  
 cin.sync(); cin.get();  return 0;
}

9. Организовать аналог "таймера" в консольном приложении, то есть, сделать так, чтобы программа выполняла некоторые действия, пока не нажата клавиша, а затем могла выполнить действие, зависящее от нажатой клавиши.

#include <stdio.h>
#include <conio.h>
#include <windows.h> 
using namespace std;
 
int main() {
 while (1) {
  while (!_kbhit()) {
   printf ("."); //делает что-то, пока не нажата клавиша
   Sleep(50); //просто чтоб не мельтешило
  }
  int c=_getch();
  if (c==27) break; //выход по ESC
  printf ("\nKey %d",c); //делает что-то в зависимости от клавиши
 }
 return 0;
}

10. Написать свой аналог функции Sleep (задержка выполнения) из библиотеки windows.h

#include <iostream>
#include <ctime>
using namespace std;
 
void mySleep(int sleepTime) {
 int curTime = clock(); //получить текущее время
 while (clock() - curTime < sleepTime) {} //ждать пока не наступит нужное время
}
 
int main () {
 cout << "start... ";
 mySleep (3000); //3 секунды
 cout << " ...stop";
 return 0;
}

11. Вывести все четырёхзначные числа-палиндромы (читающиеся одинаково слева направо и справа налево).

#include <stdio.h>
#include <stdlib.h>
 
int pal4 (int k) {
 return k%10 == k/1000 && (k%100)/10==(k%1000)/100;
}
 
int main () {
 for (int i=1000; i<10000; i++) { //вывод всех 4-значных палиндромов
  if (pal4(i)) printf ("%d ",i);
 }
 system ("pause");
 return 0;
}

Всего существует 90 четырёхзначных палиндромов, а 5-значных, к примеру, 900 - подумайте почему :)

12. "Перевернуть" целое число, записав его цифры в обратном порядке. Не использовать дополнительных строк или буферов.

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

#include <iostream>
using namespace std;
 
int reverse (int n) {
  int r = 0;
  while (n){
   r = r*10+n%10;
   n /= 10;
  }
  return r;
}

int main() {
    int n = 31240;
    cout << reverse(n);
    cin.sync(); cin.get(); return 0;
}

13. Для заданной строки найти и вывести все возможные подстроки (Си, а не C++)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *substring(char *string, int position, int length) {
 char *pointer= (char *)malloc((length+1)*sizeof(string));
 int c;
 if (pointer == NULL) {
  printf("Unable to allocate memory.\n");
  return NULL;
 }
 for (c = 0 ; c < length ; c++) {
  *(pointer+c) = *(string+position-1);      
  string++;   
 }
 *(pointer+c) = '\0';
 return pointer;
}

void substrings (char *string) {
 char *pointer;
 int position = 1, length = 1, temp, string_length;
 temp = string_length = strlen(string);
 printf("Substring of \"%s\" are\n", string);
 while (position <= string_length) {
  while (length <= temp) {
   pointer = substring(string, position, length);
   printf("%s\n", pointer);
   free(pointer);
   length++;
  }
  temp--;
  position++;
  length = 1;
 }
}

int main() {
 char *s="abcdefgh";
 substrings(s);
 fflush(stdin); getchar();
 return 0;
}

14. Заполнить квадратную матрицу по правилу, показанному на рисунке (змейкой по диагонали, начиная с правого верхнего угла).

матрица змейкой
матрица змейкой
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;

int main() {
 int n;
 cout << endl << "N=? (from 2 to 100): ";
 cin >> n;
 int mas[100][100];
 for (int i = 0; i < n; i++) {
  for (int j = n-1; j > -1; j--) {
   if ((i + j) < n) {
    mas[i][j] = 0.5 * (i + j + 1) * (i + j + 2) + 
                ((i + j) % 2 == 0 ? -j : -i);
   }
   else {
    int p = n - i - 1, q = n - j - 1;
     mas[i][j] = n * n + 1 - 
	         (0.5 * (p + q + 1) * (p + q + 2) + 
                 ((p + q) % 2 == 0 ? -q : -p));
   }
   cout << mas[i][j] << "\t";
  }
  cout << endl;
 }
 _getch();
 return 0;
}

Если в программке менять порядок обхода строк и столбцов в циклах по i,j - можно начать с другого угла.

Если менять местами выбор значений -i, -j и -q, -p в тернарном операторе - можно поворачивать в других направлениях.

15. Палиндром в массиве. В целочисленном векторе произвольной размерности найти цепочку элементов максимальной длины, в которой первое значение равно последнему, второе - предпоследнему, и т.д. Определить длину цепочки и вывести её элементы на экран.

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

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
 vector<int> v, temp, res;
 int x;
 string s;
 cout << "Input the integer numbers or empty string to exit" << endl;
 do {
  getline(cin, s);
  if (s.empty()) break;
  try {
   x = stoi(s, nullptr, 10);
  }
  catch (...) {
   cout << "Bad number format, try again, please" << endl;
   continue;
  }
  v.push_back(x);
 } while (1);
 
 for (auto it = v.begin(); it != v.end(); ++it) {
  for (auto ir = v.end(); ir != it; --ir) {
   reverse_copy(it, ir, back_inserter(temp));
   if (equal(it, ir, temp.begin()) && temp.size()>res.size()) {
    res = temp;
   }
   temp.clear();
  }
 }
 cout << "\n\nlength= " << res.size() << "\n\n";
 for_each (res.begin(), res.end(), [](int x) {
  cout << x << " "; 
 });
 cin.sync(); cin.get(); return 0;
}

16. Разлом шоколадки. Определить, можно ли от шоколадки размером n*m долек отломить k долек, если разрешается сделать один разлом по прямой между дольками (то есть, разломить шоколадку на два прямоугольника). Вводятся или задаются 3 натуральных числа: n, m и k. По условию, k не равно n*m.

Если от шоколадки размером n*m можно отломить k долек, то k должно делиться на n или на m без остатка. Также следует учесть, что при значении k, большем либо равном n*m, программа должна выдать отрицательный ответ.

#include <iostream>
using namespace std;

int main() {
 int n = 6, m = 4, k = 12;
 cout << ((k%n==0 || k%m== 0) && k<n*m ? "Yes" : "No");
 cin.sync(); cin.get(); return 0;
}

17. Фишки по краям доски. В каждую крайнюю клетку квадратной доски поставили по фишке. Могло ли оказаться, что выставлено ровно k фишек? Например, если доска имеет размеры 2*2, то может быть выставлено 4 фишки, а если 6*6, то 20.

Входные данные - натуральное число k.

Количество клеток k, соответствующее периметру квадратной доски размерностью a*a, можно найти по формуле k=a*4-4. Таким образом, введённому числу k достаточно делиться на 4 без остатка, чтобы нашлась подходящая доска. Отдельно учтём, что ноль фишек можно выставить на виртуальную доску размерностью 0*0, а 1 фишку - на доску размерностью 1*1 :)

#include <iostream>
using namespace std;

int main() {
 int k=20;
 cout << (k%4==0 || k==1 ? "Yes" : "No");
 cin.sync(); cin.get(); return 0;
}

Условие k==0 можно отдельно не проверять, так как для него выполняется k%4==0.

12.02.2016, 15:48 [12009 просмотров]


теги: c++ учебное список алгоритм

показать комментарии (1)