Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Олимпиадные задачи :/ - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ В какой кодировке getch() возвращает символ? http://www.cyberforum.ru/cpp-beginners/thread432969.html
#include <iostream> #include <Windows.h> #include <conio.h> int main() { SetConsoleOutputCP(1251); char ch; do {
C++ Почему работает не правильно? Не могу понять почему эта простенькая программка не работает как надо,подскажите почему?К примеру я ввожу 12+7= и мне выдаёт 127==? // calc.cpp: определяет точку входа для консольного приложения.... http://www.cyberforum.ru/cpp-beginners/thread432968.html
Структуры C++
Дан эллипс. Найти его площадь.(Описать тип- эллипс).????
Найти среднее арифметическое C++
Задачка... Вводится последовательность из N целых чисел. Найти среднее арифметическое его цифр (функцией оформить определения среднего арифметического цифр числа).
C++ Подпрограмма http://www.cyberforum.ru/cpp-beginners/thread432917.html
Составить подпрограмму,переписывающую старую строку в новую,так чтобы все символы были через пробел
C++ Нужно перевести программу из Паскаля в С++ К сожалению С++ только начали изучать, а программ задали много Delphi знаю хорошо Задача 1.Составить программу упорядочения по возрастанию значений в трёх переменных. Решение на Паскале uses... подробнее

Показать сообщение отдельно
Teravisor
31 / 31 / 3
Регистрация: 07.08.2011
Сообщений: 89
22.01.2012, 18:01
Первая задача:
переформулируем. Дан массив A из N элементов, изначально 0, не могут превышать 9
Дано число K
Надо найти число комбинаций распределения K вещей по N местам.
Решение:
пусть есть функция, которая распределяет T элементов по всем массивам начиная с номера U.
запускаем цикл. Начало рекурсии: U=0,T=K
функция F(T,U):
Для каждого A[U] 0<=i<=min(9,T) делаем F(T-i,U+1); Считаем сумму всех F(T-i,U+1) которые мы запускали и возвращаем.
Каждый запуск функции при Т=0 - это один из вариантов. Значит возвращаем 1 ничего не запуская. Конец рекурсии.

Если после последнего цикла T(T,N) - возвращаем 0 при T>9. Иначе 1. Второй конец рекурсии.

Написать на С++ не проблема по этому алгоритму. Кому не лень.

Edit: опечатки.

Добавлено через 21 минуту
По сути в прошлом A[U] нужен только для виду. в программе его не будет.

Вторая задача:
Дан К - сумма двух наибольших делителей.
Переформулируем:
перебрать все варианты разложения К вещей по двум полкам A[0] и A[1], так чтобы
A[0]*A[1]%B >0 для любого B больше A[0] или A[1] и меньшего K
A[0]+A[1]==K

Т.е. банально три вложенных цикла, которые ищут два числа, удовлетворяющие этим условиям. Плюс третий вложенный в них цикл по поиску B, которое бы удовлетворяло A[0]*A[1]%B==0. Ответом будет их сумма. Это если писать на скорость.
Даже распишу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Function(int K)
{
   int A0=0;
   int A1=0;
   for(A0=K;A0>0;A0--)
       for(A1=K;A1>0;A1--)
       {
//Тут мы не будем использовать math::min или другие библиотеки. Поэтому так.
          if(A0==A1)continue;
          for(int B=K;a>0;a--)
          {
              if((A0*A1%B)==0)break;
              if((B<A0)&&(B<A1))return A[0]+A[1];
          }
       }
//Такого числа нет.
   return -1
}
Вроде так.

З.Ы. можно сделать циклы A0 и A1 >1 т.к. если одно из них равно 1, то строка 12 всегда сработает. Можно еще 14й строкой вставить else break;
Увеличит производительность, но для олимпиадных оно не требуется вроде?
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru