Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вариации подстроки в строке. 
:(
    Опции темы
.talisman
Дата 22.5.2005, 11:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
Задача:
Подсчитать колличество слов длины К из данных N букв, не содержащих данное подслово.

есть символьные массивы:
А и Б.
Оба вводятся с клавиатуры в ходе выполнения программы. Строка Б является подстрокой А. Еще есть переменная len, которая определяет длину искомого слова. Например:

пользователь вводит строку: "abcd".
подстроку: "bc".
длину слова: "3".

формируем слова:
abc -- bc имеет место приутствовать, каунт не увеличиваем.
abd -- bc нет, увеличиваем каунт на единицу.
bcd -- bc есть, каунт не увеличиваем.

Общий алгоритм:
1. Получаем данные.
2. Формируем новые строки.
3. Проверяем содержание подстроки в новых строках и если она есть, то увеличиваем каунт.
4. записываем в файл.

Вопрос:
как перебрать всевозможные коомбинации при формировании новой строки? (порядок букв менять нельзя, то есть в предыдущем примере подстроки типа dcb нет).

заранее спасибо.
PM MAIL   Вверх
maxim1000
Дата 22.5.2005, 13:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
насколько я понял, каждое получаемое слово задается тем, какие буквы мы выкидываем, а какие оставляем (т.к. порядок менять нельзя)
можно воспользоваться рекурсией (дальше, если есть желание, можно заняться оптимизацией):
Код

int f(string s,int i,int k,string Alphabet,string Target)
{
  if(s.length()==k)//одно из слов длины K
  {
    if(s.Contains(Target))//если содержит слово - не подходит
      return 0;
    else//а если нет - то, что надо
      return 1;
  }
  if(i==Alphabet.length())//нечего больше добавлять (исходное слово закончилось)
    return 0;
  int count=0;
  count+=f(s,i+1,k,Alphabet,Target);//соотв.случаю, когда мы не добавляем текущую букву
  count+=f(s+Alphabet[i],i+1,k,Alphabet,Target);//когда добавляем
  return count;
}
...
  //где-то в далекой функции main()
  result=f("",0,k,"qwert","wt");

если сделать класс string с нужными методами, то эта программка может даже скомпилироваться smile

Это сообщение отредактировал(а) maxim1000 - 22.5.2005, 13:31


--------------------
qqq
PM WWW   Вверх
Akina
Дата 23.5.2005, 07:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
Опять элементарная задачка... ДУМАЙ!!! а не программы пиши... формула получается ВПРЯМУЮ...


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
segmentation_fault
Дата 23.5.2005, 18:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 82
Регистрация: 14.2.2005
Где: в интернете

Репутация: нет
Всего: 1
Ну формула-то впрямую получается, но это уже больше математика чем информатика. Может их препод хочет именно чтобы они алгоритм написали, а не нашли формулу и вставляли туда нужные значения.
PM MAIL   Вверх
.talisman
Дата 24.5.2005, 06:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
формула надо, так как комбинаторику проходим. учится осталось три дня, а лаба еще не сдана.
дай плиз формулу =)
обещаю все потом выучить =)
PM MAIL   Вверх
.talisman
Дата 24.5.2005, 11:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
насчет всех подслов фуормулу нашел:
(m!)/(n!-(m!-n!), где m длина строки, а n длина генерируемых слов.

в предыдущем примере m=4, а n=3. Получаем:
(4!)/(3!-(4!-3!) = 4!/3! = 4.

а вот как вычесть строки содержащие введенную подстроку я не знаю =(
PM MAIL   Вверх
Akina
Дата 24.5.2005, 11:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
А какая разница - слова в строке или подстрока в слове?


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
.talisman
Дата 24.5.2005, 11:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
что-то я не понял вашего вопроса.
разницы никакой, но какое отношение этот пример имеет к данному случаю?

хотя нет, разница в том, что слова в строке разделены пробелами.
PM MAIL   Вверх
Akina
Дата 24.5.2005, 12:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
Цитата
насчет всех подслов фуормулу нашел:

Только неправильную. С арифметикой сложности... приведи подобные, получится 1, независимо от m и n... уж как ты там подстановку сделал и посчитал не то что на самом деле получается...

Цитата
слова в строке разделены пробелами

Слово - совокупность символов. Пробел - такой же символ, как буква, цифра или там запятая, пока не определен его специальный статус. В твоем задании он НЕ определен. Мысли абстрактнее...


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
.talisman
Дата 24.5.2005, 12:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
так ничего и не понял smile
если делать абстрактно и просто найти кол-во всевозможным подслов заданной длины, то я не понимаю как проверить, какие подслова содержут подстроку, а какие нет.
PM MAIL   Вверх
.talisman
Дата 24.5.2005, 14:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
по совету maxim1000 попробовал воспользоваться рекурсией.
писалось в борлан си++ 3.1, 1992 года, досовская =)

проблема -- результат всегда равен нулю.
Код
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>
#include <string.h>

int f(char *s,int i,int len,char *a1,char *a2)
{
    if(strlen(s)==len)
    {
        if(strstr(s, a2))
            return 0;
        else
            return 1;
    }
    if(i==strlen(a1))
        return 0;
    int count=0;
    char tmp[5];
    tmp[0]=a1[i];
    tmp[1]=NULL;
    count+=f(s, i+1, len, a1, a2);
    count+=f(tmp, i+1, len, a1, a2);
    return count;
}

void main()
{
    char a1[20], a2[20];
    int len, result;
    clrscr();
    printf("enter string: ");
    scanf("%s", a1);
    printf("enter substring: ");
    scanf("%s", a2);
    printf("enter lenght of generic word: ");
    scanf("%i", len);
    result=f("", 0, len, a1, a2);
    printf("%i", result);
    getch();
}
PM MAIL   Вверх
maxim1000
Дата 25.5.2005, 03:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
по-моему, здесь получилось не совсем то, что я предполагал:
Цитата
count+=f(s+Alphabet[i],i+1,k,Alphabet,Target);//когда добавляем

Цитата
count+=f(tmp, i+1, len, a1, a2);

в алгоритме в функцию передается строка с добавлением одного символа
а в реализации передается строка из одного символа
тут надо было бы выделить память (new или массивом) под новую строку, записать туда старую и добавить еще один символ
можно вообще использовать один буфер для всех вызовов: просто сделать его достаточно большим (k+1 должно хватить), и перед вторым рекурсивным вызовом добавлять туда символ, а после - удалять (т.к. этот буфер используется и предыдущими вызовами)
Код

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

int f(char *s,int i,int len,char *a1,char *a2)
{
    if(strlen(s)==len)
    {
        if(strstr(s, a2))
            return 0;
        else
            return 1;
    }
    if(i==strlen(a1))
        return 0;
    int count=0;
    count+=f(s, i+1, len, a1, a2);
    {//add an a1[i] to s
      char *p=s;
      while(*p)
        p++;
      *p++=a1[i];
      *p=0;
    }
    count+=f(s, i+1, len, a1, a2);
    {//clean up:remove last character from s
      char *p=s;
      while(*p)
        p++;
      p--;
      *p=0;
    }
    return count;
}

void main()
{
    char a1[20], a2[20];
    char s[100];
    int len, result;
    printf("enter string: ");
    scanf("%s", a1);
    printf("enter substring: ");
    scanf("%s", a2);
    printf("enter lenght of generic word: ");
    scanf("%d", &len);
    s[0]=0;
    result=f(s, 0, len, a1, a2);
    printf("%i", result);
    getch();
}

P.S.
кстати, когда с помощью scanf читается число, надо давать адрес переменной для созранения результата - перед len надо ставить &...


--------------------
qqq
PM WWW   Вверх
.talisman
Дата 25.5.2005, 14:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 19.2.2005

Репутация: нет
Всего: нет
огромное спасибо.
насчет амперсанда знал, опечатался =)
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1052 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.