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

Комбинаторика, количество анаграмм - C++

Восстановить пароль Регистрация
 
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
29.08.2012, 12:41     Комбинаторика, количество анаграмм #1
Здравствуйте, решаю задачу, но не знаю какой цикл использовать и как его задать. Суть задачи проста, в консоль вводят слово, далее подсчитуем количество символов, потом необходимо подсчитать факториал из длины строки, а потом проходя по циклу нужно искать одинаковые буквы (елементы), а потом в зависимости от количества одинаковых елементов, нужно поделить до этого полученый факториал на количество одинаковых букв.
Например,
Вводим
Код
SOLO
Далее считаем количество букв (4), считаем факториал из 4 (24), а потом уже идет цикл, который исчет одинаковые буквы (2="ОО"), а потом делит на количество букв, что повторяються (2). В итоге получаем 24/2=12 это и есть нужный и правильный ответ
Код
Выходные данные:
12
Вот, набросок подсчет длинны и факториала, а вот цикла не хватает.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
using namespace std;
double fact(unsigned long n);
int main()
{
    char s[14];
    scanf("%s", &s);
    int d=strlen(s);
    printf("%u\n",d);
           int x=fact(d);
 
    
    return 0;
}
double fact(unsigned long n)
{
    double c=(n<1)?1:n;
    if (1<(n-=1))
        c*=fact(n);
    return c;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2012, 12:41     Комбинаторика, количество анаграмм
Посмотрите здесь:

Поиск анаграмм во входном файле C++
Комбинаторика C++
C++ Поиск анаграмм
Группы анаграмм в строке C++
Строка: Поиск анаграмм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
29.08.2012, 12:58     Комбинаторика, количество анаграмм #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
По-быстрому закодил и проверил на ******** - прошло все тесты.

Версия с файлами
C++
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
#include <fstream>
#include <string>
 
_int64 fact (int n)
{
    if (n==0 || n==1) 
        return 1;
    return fact(n-1)*n;
}
 
std::ifstream ifs ("input.txt");
std::ofstream ofs ("output.txt");
 
int main()
{
    std:: string s;
    ifs >> s;
    int mas[27] = {0};
 
    for (int i=0; i<s.length(); ++i)
        mas[s[i] - 'a']++;
 
    _int64 tmp = fact (s.length());
    for (int i=0; i<27; ++i)
        tmp /= fact(mas[i]);
    ofs << tmp;
    return 0;
}


Версия без файлов
C++
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
#include <iostream>
#include <string>
 
_int64 fact (int n)
{
    if (n==0 || n==1) 
        return 1;
    return fact(n-1)*n;
}
 
int main()
{
    std:: string s;
    std::cin >> s;
    int mas[27] = {0};
 
    for (int i=0; i<s.length(); ++i)
        mas[s[i] - 'a']++;
 
    _int64 tmp = fact (s.length());
    for (int i=0; i<27; ++i)
        tmp /= fact(mas[i]);
    std::cout << tmp;
    system ("pause");
    return 0;
}


Я просто завел массив, в котором mas[i] показывает, сколько раз встречалась в строке буква, позиция которой в алфавите i. Считал я это, проверяя каждый символ строки и увеличивал кол-во таких символов.

P.S. если во входной строке заглавные буквы, то вместо mas[s[i] - 'a']++; напишите mas[s[i] - 'A']++;
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
29.08.2012, 13:08  [ТС]     Комбинаторика, количество анаграмм #3
Хмм, а вообще не известно заглавная ли буква, или нет! Что тогда?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
29.08.2012, 13:09     Комбинаторика, количество анаграмм #4
Вообще-то должно быть известно, но если нет, то переводите заглавную в нижний регистр.
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
29.08.2012, 13:42  [ТС]     Комбинаторика, количество анаграмм #5
А вы можете объяснить, команду length() в частности, и её использование в цикле, я просто привык через strlen()? Да, и в чем отличие между этими командами и где лучше использовать ту или иную команду?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
29.08.2012, 13:46     Комбинаторика, количество анаграмм #6
s.length()
Yandex
Объявления
29.08.2012, 13:46     Комбинаторика, количество анаграмм
Ответ Создать тему
Опции темы

Текущее время: 02:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru