Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/15: Рейтинг темы: голосов - 15, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24

Формула сочетаний из n по k, выразить n

17.10.2017, 19:38. Показов 3327. Ответов 13
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день. Есть следующая задача:
Кликните здесь для просмотра всего текста

Все в мире знают, что число сочетаний из N по K есть C = N! / (K! * (N - K)!) и что 0! = 1.
Икар и Глеппе этого не знали. Сегодня они проходили эту тему в школе. К превеликому сожалению, листок, состоящий из m строк вида N, K, C (N - целое от 1 до 33 включительно, K - целое от 0 до N включительно, все строки были различны), промок, и первое число каждой строки утерялось. Помогите ребятам восстановить эту ценную информацию.

Формат файла входных данных:
В первой строке входного файла записано количество строк на листочке m (m - целое от 1 до 600), далее идет m строк, оставшихся от листочка.

Формат файла выходных данных:
В выходной файл выведите в отдельной строке, чему могло быть равно N. Если вариантов несколько, выведите наименьший.

Насколько я понимаю, задача сводится к тому, чтобы выразить из формулы N, но как-то собственно сделать и реализовать?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
17.10.2017, 19:38
Ответы с готовыми решениями:

Вычислить количество сочетаний из N сочетаний по K
Делаю на Dosbox. Можете написать на Assembler. Спасибо! Вычислить количество сочетаний из N сочетаний по K. C=N!/(K!*(N-K)!)

Формула: дроби (числитель и знаменатель той же высоты, что и вся формула)
Всем доброго времени суток! Многие сталкивались с тем, что, при создании формул, числитель и знаменатель дроби уменьшаются. Собственно...

Формула полной вероятности и формула Байеса
Помогите пожалуйста Два стрелка Иванов и Петров, имеющие по два заряда, поочерёдно стреляют в мишень. Вероятность попадания при одном...

13
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
17.10.2017, 23:56
Цитата Сообщение от Ma3stro Посмотреть сообщение
N - целое от 1 до 33 включительно
Заводите массив от 0 до 33 для хранения N! для каждого значения N. Далее для каждой строки перебираете N по массиву. В таком случае не потребуется каждый раз считать факториал. Когда найдете N - переходите к следующей строке.
1
 Аватар для tmpValue
41 / 75 / 15
Регистрация: 04.10.2017
Сообщений: 283
18.10.2017, 01:45
Цитата Сообщение от Ma3stro Посмотреть сообщение
Насколько я понимаю, задача сводится к тому, чтобы выразить из формулы N, но как-то собственно сделать и реализовать?
N никак не выведешь формулой. Но факториал запросто.
https://www.cyberforum.ru/cgi-bin/latex.cgi?C = \frac{n!}{k!\(n - k\)!} \Rightarrow n! = Ck!\(n - k\)! \Rightarrow \frac{n!}{\(n - k\)!} = Ck!
Учитывая выше изложенное, берешь на вооружение совет JIeIIIa, считаешь сначала правую часть уравнения, потом от значения k бежишь вверх по массиву и считаешь левую часть. Таким образом ты вычислишь n!, ну а n будет равна соответственно индексу найденного в массиве значения.
1
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 18:46  [ТС]
Сделал следующим образом:
Кликните здесь для просмотра всего текста
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
 
        int countLine = in.nextInt(); //читаем первое значение - количество строк
 
        for(int i = 0; i < countLine; i++) { //цикл на количество строк
            byte k = in.nextByte();
            long C = in.nextLong();
 
            for(int j = 0; j < 34; j++) { //34, потому что из условия сказано, что искомое число меньше 34
                if(combination(j, k) == C) {
                    out.println(j); //Если совпадает, то выводим в файл, а далее продолжается цикл по количеству строк
                    break;
                }
            }
        }
        out.close();
    }
 
    private static long fact(int n) { //метод вычисления факториала (используется в методе ниже)
        long ret = 1;
        if(n == 0) return 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
 
    private static long combination(int n, int k) { //та самая формула, которая выдает нам количество сочетаний
        return fact(n) / (fact(k) * fact(n - k));
    }
}

Тесты у меня проходит, но когда отправляю в проверяющую систему, говорит мол неверный ответ. Может быть значение из их проверяющей системы не влазит в long и следует использовать BigInteger?
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
18.10.2017, 18:49
Скорее тесты по времени не проходят.
Зачем Вы в 36-ой строке каждый раз считаете факториал? Я же говорил как следует поступить.
0
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 18:52  [ТС]
Нет-нет, в условии сказано, что для этой задачи один единственный тест.
Ошибку мне выдало "Wrong Answer", и что-то мне подсказывает, что дело в типах данных
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
18.10.2017, 18:55
Ma3stro, сколько у Вас выполняется тест из 600 строк? Если проверяющая программа за указанное время не получает ответа, то вполне может говорить, что ответ не верный. Можете попробовать "подсунуть" бесконечный цикл и посмотреть что получите в ответ.
0
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 19:01  [ТС]
Да, действительно. Ограничение стоит в 1 секунду.
Но как можно оптимизировать 600 строк до выполнения в 1 секунду, в которых могут попадаться не самые маленькие числа?
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
18.10.2017, 19:02
Цитата Сообщение от JIeIIIa Посмотреть сообщение
Заводите массив от 0 до 33 для хранения N!
Когда вычисляете C из n по k не считаете факториал, а берете значения из массива.
0
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 19:14  [ТС]
Вот, сделал так, все так же "неверный ответ"
Кликните здесь для просмотра всего текста
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
 
        int countLine = in.nextInt();
 
        for(int i = 0; i < countLine; i++) {
            byte k = in.nextByte();
            long C = in.nextLong();
 
            for(int j = k; j < 34; j++) {
                if(combination(j, k) == C) {
                    out.println(j);
                    break;
                }
            }
        }
        out.close();
    }
 
    private static long fact(int n) {
        long ret = 1;
        if(n == 0) return 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
 
    private static long combination(int n, int k) {
        long[] factN = new long[34];
        for(int i = 0; i < 34; i++)
            factN[i] = fact(i);
 
        return factN[n] / (factN[k] * factN[n-k]);
    }
}
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
18.10.2017, 19:16
Сделали тоже, только в профиль.
factN делаете полем класса и вычисляете его ОДИН раз в самом начале. Сейчас же Вы массив factN пересчитываете каждый раз, когда вызываете combination
0
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 19:27  [ТС]
Ай, да что с ним не так
Кликните здесь для просмотра всего текста
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
 
        int countLine = in.nextInt();
 
        long[] factN = new long[34];
        for(int i = 0; i < 34; i++)
            factN[i] = fact(i);
 
        for(int i = 0; i < countLine; i++) {
            byte k = in.nextByte();
            long C = in.nextLong();
 
            for(int j = k; j < 34; j++) {
                if(factN[j] / (factN[k] * factN[j-k]) == C) {
                    out.println(j);
                    break;
                }
            }
        }
        out.close();
    }
 
    private static long fact(int n) {
        long ret = 1;
        if(n == 0) return 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}
0
 Аватар для tmpValue
41 / 75 / 15
Регистрация: 04.10.2017
Сообщений: 283
18.10.2017, 20:13
Лучший ответ Сообщение было отмечено Ma3stro как решение

Решение

Цитата Сообщение от Ma3stro Посмотреть сообщение
Может быть значение из их проверяющей системы не влазит в long
Ну а сам как думаешь?
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> def f(n):
...     a = 1;
...     while n > 0:
...             a *= n
...             n -= 1
...     return a
... 
>>> f(0)
1
>>> f(10)
3628800
>>> f(20)
2432902008176640000
>>> f(30)
265252859812191058636308480000000
>>> f(33)
8683317618811886495518194401280000000
>>>
Добавлено через 44 минуты
Ma3stro, держи
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package samples;
 
import java.util.*;
import java.math.*;
import java.io.*;
 
public class Samples {
    public static void main(String[] args) {
        // TODO code application logic here
        
        // итак, пусть искомое n = 33; k = 30;
        // k! = 265252859812191058636308480000000
        // n! = 8683317618811886495518194401280000000
        // тогда C = 5456;
        // готовим свой массив
        int C = 5456;
        int k = 30;
        BigInteger foo[] = fillFields();
        
        // ищем выражение n!/(n - k)!
        BigInteger tmp = (new BigInteger(Integer.toString(C))).multiply(foo[k]);
        
        // ищем n
        for (int i = k; i < foo.length; i++) {
            if ((foo[i].divide(foo[i - k])).compareTo(tmp) == 0){
                k = i;
                break;
            }
        }
        
        System.out.println(k);
    }
    
    static BigInteger[] fillFields () {
        BigInteger a[] = new BigInteger[34];
        int i = 1;
        
        a[0] = new BigInteger("1");
        
        while (i < 34) {
            a[i] = a[i - 1].multiply(new BigInteger(Integer.toString(i)));
            i++;
        }
        return a;
    }
}
1
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 24
18.10.2017, 22:17  [ТС]
Работает просто прекрасно, благодарю.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.10.2017, 22:17
Помогаю со студенческими работами здесь

Формула полной вероятности и формула Байеса
Здравствуйте! Решала задачу по теории вероятности, но ответ не сошелся. Подскажите, пожалуйста, что неправильно:) Произведено 3...

Формула полной вероятности. Формула Байеса
Из урны, где было 4 белых и 6 черных шаров, потерян один шар неизвестного цвета. После этого из урны извлечены (без возвращения) два...

Формула полной вероятности. Формула Байеса
В медицине установлен факт, что некоторое тяжелое неврологическое заболевание в разной степени характерно для мужчин и женщин в некотором...

Формула полной вероятности и формула Байеса
Каждому из 3 первоклассников - Пете, Коле и Мише - предложили одинаковое количество загадок. Петя отгадывает в среднем 3 загадки из 4. Коля...

Формула полной вероятности. Формула Байеса
3.5. На четырех станках при одинаковых и независимых условиях изготавливают детали одного наименования. На первом станке изготавливают 15%,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru