Задача из Кернигана и Ритчи: Напишите программу, печатающую гистограмму длин слов из файла ввода. Не нужно готовое ...

09.04.2010 в 10:19

Я знаю, что я гений, но мне от этого ничуть не легче.

язык? какие технологии допустимо использовать?

URL

09.04.2010 в 10:24

Керниган и Ритчи - это язык Си. Я пользуюсь компилятором среды Borland. В задаче нужно использовать массивы.
khpi-iip.mipk.kharkiv.edu/library/pgm/kr/c_1.ht...

URL

09.04.2010 в 11:01

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

кто такие Керниган и Ритчи я знаю, сам по распечатке этой книги Си учил

(в 90-м книжку купить было оочень сложно). Но одно дело задача из книжки, а другое дело, на чем её решать

А вообще, подход очень прост. заводим int-ый массив достаточной длины (можно реализовать и динамический, но это наверно не входит в цель этой задачи), размер массива соответствует максимальной длине слова (которую можно посчитать, пройдясь по всему файлу, но, опять же, оверхед).
потом читаем файл посимвольно. Пока читаем буквы - инкрементируем счетчик, как поймали пробел, перевод строки и т.п. - инкрементируем значение ячейки массива, соответствующей длине только что прочитанного слова, счетчик длины сбрасываем.
Далее вопрос лишь в том, как лучше вывести гистограмму, ибо в Си нет встроенных возможностей рисовать графики.
Можно просто вывести построчно массив, отобразив нормированное значение каждой ячейки соответствующим количеством символов '='. Для нормировки находим самую частую длину из нашего массива и делим её на ширину "графика" (например, 60). Потом в каждой строке на экране пишем номер ячейки массива (форматируем на ширину 6 с правым выравниванием), ставим вертикальную черту, потом рисуем знаки '=' в количестве, равном значению из ячейки, разделённому на вычисленный нормировочный коэффициент.

URL

09.04.2010 в 11:19

Jariad

mikluho спасибо! Вообще то понятно, но код я пока по этим инструкциям сам написать не смогу. Был бы благодарен за помощь в написании кода с "разжёвыванием".

Я видел решение этой задачи так: Считавыем файл ввода. Вместо каждого символа выводим на печать знак "=". Как только натыкаемся на пробел, прыгаем на новую строку. Должна выйти гистограмма из знаков равно. Но, где тут тогда массивы?

URL

09.04.2010 в 11:32

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy, фокус в том, что гистограмма - это статистический график. Он должен отразить соотношение слов с разной длиной. т.е. в массиве после прочтения надо получить, сколько было в файле слов с длиной 1,2,3 и т.д. Например, {1-17, 2-6, 3-12, 4-34, 5-22, 6-18, 7-10, 8-6, 9-2}
получится такое:

1|=====
2|==
3|===
4|==========
5|=======
6|======
7|===
8|==
9|=

URL

09.04.2010 в 14:32

Jariad

Для нормировки находим самую частую длину из нашего массива и делим её на ширину "графика" (например, 60). Потом в каждой строке на экране пишем номер ячейки массива (форматируем на ширину 6 с правым выравниванием), ставим вертикальную черту, потом рисуем знаки '=' в количестве, равном значению из ячейки, разделённому на вычисленный нормировочный коэффициент.

Я не пойму, зачем эти ухищрения? Почему нельзя просто вывести построчно ячейки массива, заменив каждое к-во инкрементов на знак "="? Допустим, у меня массив:

int  ndigit[10];

for (i = 0; i < 10; ++i)

  ndigit[i] = 0;

while ((c = getchar()) != '\n')

  if (c >= '0' && c <= '9')

      ++ndigit[c-'0'];

printf("=");

     for (i = 0; i < 10; ++i)

Предположим, в файле ввода два слова, одно - длиной три буквы, второе - 5 букв, результат:
1|
2|
3|=
4|
5|=
6|
7|
8|
9|

URL

09.04.2010 в 14:40

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy, а если в файле будет 200 слов их 4-х букв?
Я не пойму, зачем эти ухищрения? - это что бы весь график поместился на экране

URL

10.04.2010 в 13:00

Jariad

Как инкриминировать значение ячейки массива?

URL

10.04.2010 в 14:25

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy

ndigit[i]+=1;

URL

12.04.2010 в 10:13

Jariad

Вот такой код накрапал:

#include <stdio.h>
#include <conio.h>

    main() 
  {

       int  ndigit[10];
       int c, i, a1, aa;
       for (i = 0; i < 10; ++i)
            ndigit[i] = 0;

       while ((c = getchar()) != '\n'){
        i = 0;
           while ((c = getchar()) != ' ')
           ++i;

        ++ndigit[i];
       }



     printf("digits =");
     for (i = 0; i < 10; ++i) {
     aa = i +1;
        printf("\n i =  %d = ", aa);
        printf("%d    ", ndigit[i]);


                for (a1=ndigit[i];a1 > 0; --a1){
                         printf("%d", 0);
                }
     }





                   getch();
  }

URL

12.04.2010 в 22:30

Слушатель

Don't stop the music.

_Dimitriy

Давайте разбираться:

В условии внешнего while функция getchar() считала литеру с экрана и запихнула её в переменную c. После этого обнулился i, в следующем while, была считана следующая литера, далее пошёл счёт сколько их до пробела после чего запихивание значения в массив.

Например для ввода: mama_\n (символ '_' - означает пробел), getchar() считает 'm', потом считает 'a' и отсчёт пойдёт начиная с 'a' (включительно). Насчитаем до пробела 3 буквы и инкрементируем значение ndigit[3].

Таким образом программа должна выдать ошибочный вывод (..., i = 3 = 1, i = 4 = 0, ...).

Ваша программа выдаёт верный вывод, но это только потому что вы "мошенничаете" ). А именно, вы для счётчика aa = 4 (aa = i + 1) выдаёте то что сидит в массиве для i = 3, таким образом ответ верный но достигается за счёт ухищрений с индексом и счётчиком, что является признаком плохого кода (труден для быстрого понимания и модификации). Не говоря уже о том что в массиве сидят неверные значения.

Проблема в том что программа "глотает" одну литеру на входе (есть ещё проблемы но о них позже. Эта главная.).

Как её решить?

URL

13.04.2010 в 03:27

Слушатель

Don't stop the music.

...после чего запихивание значения в массив.

Прошу прощения, описался. Должно быть: после чего инкрементация значения ячейки массива по соответствующему индексу i.

URL

13.04.2010 в 10:36

Jariad

Слушатель спасибо!
Я не знаю, как решить эту проблему. Можно какие-нибудь подсказки?

URL

13.04.2010 в 12:42

Слушатель

Don't stop the music.

_Dimitriy
спасибо!
Пока не за что.

Я не знаю, как решить эту проблему
Да вы не теряйтесь

. Внимательно прочитайте ещё раз моё объяснение (возможно оно многословно, но я просто не знаю как написать короче, понятней но не выложить вам готовое решение). Прочитайте и напишите с какого места вы перестали понимать о чём идёт речь. Я готов отвечать по каждому предложению.

Если вы поняли объяснение то как решить эту проблему вам должно быть понятно.

Можно какие-нибудь подсказки?
Как подсказать ещё более прозрачно - я не знаю.

URL

13.04.2010 в 12:45

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy мм.. уж не знаю, что тут ещё подсказывать.. у меня получилась такая программа:

#include <stdio.h>
#include <tchar.h>
#include <io.h>
#include <string.h>



bool isEmptySpace(char c)
{
	if(c==' ' || c=='\r' || c=='\n' || c=='\t' || c=='.' || c==',' || c=='-')
		return true;

	return false;
}

int main(int argc, char* argv[])
{
	const int MAXLEN=30;
	const int MAXWIDTH=60;

	if(argc<2)
	{
		printf("no file name specilied!\n");
		return 1;
	}

	FILE *stream;

   if( (stream  = fopen( argv[1], "r" )) == NULL )
   {
      printf( "The file %s was not opened\n", argv[1] );
	  return 2;
   }

   int c;
   int count;
   int wordsLen[MAXLEN];
   for(count=0;count<MAXLEN;count++) wordsLen[count]=0;

   char strBlank[MAXWIDTH+1];
   strBlank[MAXWIDTH]=0;
   _strset(strBlank,' ');
   char strPrint[MAXWIDTH+1];
   strPrint[MAXWIDTH]=0;
   _strset(strPrint,' ');


   count=0;

   c=fgetc(stream);

   while( !feof( stream )){
	   
	   if(!isEmptySpace((char)c))
		   count++;
	   else
	   {
		   if(count>=MAXLEN-1)
			   wordsLen[MAXLEN-1]+=1;
		   else
			   wordsLen[count]+=1;

		   count=0;
	   }

	   c=fgetc(stream);
   }
		   if(count>=MAXLEN-1)
			   wordsLen[MAXLEN-1]+=1;
		   else
			   wordsLen[count]+=1;


   fclose(stream);

   int max=0;
   double norm;

   for(count=0;count<MAXLEN;count++)
   {
	   if(wordsLen[count]>max)
		   max=wordsLen[count];
   }

   norm=max/(double)MAXWIDTH;
   //printf("max=%3d|%f\n",max, norm);


   for(count=1;count<MAXLEN;count++)
   {
	   int len=wordsLen[count]/norm;

	   strcpy( strPrint, strBlank ); 
	   _strnset(strPrint, '=', len);

	   printf("%3d|%s|%d\n",count, strPrint, wordsLen[count]);
   }

	return 0;
}

для моего первого комментария с объяснениями получается вот что:

  1|===========================                                 |17
  2|======================================                      |24
  3|========================                                    |15
  4|===================                                         |12
  5|===============================================             |29
  6|============================================================|37
  7|=========================                                   |16
  8|==============                                              |9
  9|========                                                    |5
 10|========                                                    |5
 11|===========                                                 |7
 12|===========                                                 |7
 13|====                                                        |3
 14|====                                                        |3
 15|===                                                         |2
 16|                                                            |0
 17|                                                            |0
 18|                                                            |0
 19|                                                            |0
 20|                                                            |0
 21|                                                            |0
 22|                                                            |0
 23|                                                            |0
 24|                                                            |0
 25|                                                            |0
 26|                                                            |0
 27|                                                            |0
 28|                                                            |0
 29|                                                            |0

URL

13.04.2010 в 13:01

Слушатель

Don't stop the music.

mikluho
Человек на 1-й главе K&R

, а там ещё нет строковых констант, функций, передачи параметров в main, const-ов, и уж тем более работы с файлом и со строками.

URL

13.04.2010 в 13:22

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

Слушатель,я не знаю ни где он, ни на чём пишет (диалектов С/С++ и платформ не счесть).. суть в алгоритме.

URL

13.04.2010 в 14:48

Jariad

Может, задать два условия в одной функции?

URL

13.04.2010 в 14:53

Слушатель

Don't stop the music.

_Dimitriy
То есть?

URL

13.04.2010 в 19:21

Jariad

Убрать переменную "с" из первого while?

URL

14.04.2010 в 02:47

Слушатель

Don't stop the music.

_Dimitriy
Допустим. Получим:

while (getchar() != '\n')
{
        i = 0;
        while (c = getchar() != ' ')
        {
                ++i;
        }
        ndigit[i]++;
}

Как и раньше, функция getchar считала первую литеру и не запомнила её, счётчик i стал равен нулю. Далее во внутреннем while функция getchar считала вторую литеру, занесла её в переменную c, и пошёл подсчёт опять начиная со 2-й литеры. Проблему не решило.

Как сделать чтобы сначала мы проверили первую считанную и запомненную литеру, убедились что она не является пробелом, увеличили счётчик потом считали бы следующую занесли бы её и далее по циклу до пробела?

URL

14.04.2010 в 06:43

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

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

       i = 0;
       c = getchar();
       while (c != '\n')
      {
           if(c != ' ')
               ++i;
           else
           {

                ++ndigit[i];
                i=0;
           }
           c = getchar();
       }

URL

14.04.2010 в 10:23

Слушатель

Don't stop the music.

mikluho
Послушайте, перестаньте пожалуйста мешать.

Я прекрасно понимаю, что вы замечательный и опытный программист, решили эту задачу за несколько секунд в уме и знаете несколько различных способов её решения. Но:

Своё умение помочь вы продемонстрировали 2010-04-13 14:45 написав код с использованием разных ненужных в данном случае свойств. Когда я вам на это аргументировано указал вы отписались, что вы не знаете полноты ситуации и "суть в алгоритме". Я не спорю попусту и беспредметно поэтому я ничего не сказал в ответ.

Вы даже не дали себе труда заглянуть в поисковик и посмотреть к какой главе относится эта задача (занимает меньше одной минуты), написали очень красиво и грамотно выглядящую программу и что дальше? Вы помогли? Нет. Зачем вы это сделали?

Сейчас вы написали код с применением умных выражений, "разделяй и властвуй" (спасибо хоть про MVC не написали), который выглядит понятно новичку но неправильный (почему неправильный - потому что skip литер с инкрементацией, желательно делать через внутренний цикл а не присобачив if-ы, и почему-то инкрементируя и тут-же на следующей строке обнуляя счётчик. Это дико выглядит. Пожалуйста не отвечайте по этому поводу т.к. ваши соображения я читать не буду). Этот код неправильный и что самое опасное понятный новичку. Потому что возможно новичок ваш код поймёт и будет в дальнейшем так писать решая например задачу "убрать все лишние пробелы между строками". Вы об этом задумывались? Вряд ли. Зачем вы написали этот код?

Из этих двух промахов допущенных вами, я делаю вывод, что помочь вы в данном случае - не можете. Поэтому вторично прошу вас не мешать. В противном случае, если я увижу ещё один ваш адресуемый новичку пост - я отписываюсь от этого треда и оставляю работу помогать вам. Всего хорошего.

URL

14.04.2010 в 11:46

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

Слушатель, во-первых, я не знаю текущий уровень знаний _Dimitriy в области программирования. Возможно с первым примером я и переборщил...
во-вторых, я изначально попытался описать алгоритм подсчета словами (читаем файл посимвольно. Пока читаем буквы - инкрементируем счетчик, как поймали пробел, перевод строки и т.п. - инкрементируем значение ячейки массива, соответствующей длине только что прочитанного слова, счетчик длины сбрасываем.), но возникла сложность с его реализацией. Видимо _Dimitriy не смог разделить чтение из файла и подсчет символов, из-за чего и "пропадали" символы.
Вы привели вариант кода, которые не решает проблему.
Я предложил разложить алгоритм на простейшие составляющие, которые и перечислил. Чем вреден данный подход - мне не известно.
Далее я привел код, который отражает мои предложения, хотя возможно стоило предложить блок-схему алгоритма? По идее именно с них надо начинать обучение программированию...

ps
почему неправильный - потому что skip литер с инкрементацией, желательно делать через внутренний цикл а не присобачив if-ы, и почему-то инкрементируя и тут-же на следующей строке обнуляя счётчик. - Это Ваше имхо. Вы подумали, что будет с этим вашим скипом, если последний символ будет не пробел, а перевод строки?

URL

14.04.2010 в 11:59

Jariad

Может, можно отсчёт начинать с единицы?

i = 1;

URL

14.04.2010 в 12:43

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy, хоть меня тут уже попинали

, но всё же, мой Вам совет, не надо пытаться "сломать" алгоритм так, что бы он начал выдавать правильный результат. Это то же самое, что и подгонка решения задачи под ответ в конце учебника. Попробуйте расписать алгоритм в виде блок-схемы, а потом написать код, соответствующий схеме.

URL

14.04.2010 в 12:52

Jariad

Спасибо mikluho , но вы уже, вроде, предоставили отличную блок-схему. Вся проблема сейчас, я так понимю, в "заглатывании" первого символа. Так как, можно начинать отсчёт с единицы?

URL

14.04.2010 в 13:02

mikluho

Я знаю, что я гений, но мне от этого ничуть не легче.

_Dimitriy Так как, можно начинать отсчёт с единицы? - этот подход будет выдавать неправильный результат при обнаружении нескольких пробелов подряд. (два пробела дадут слово длиной 1, три пробела - два таких слова т.д.)

URL

14.04.2010 в 16:09

Слушатель

Don't stop the music.

mikluho
но всё же, мой Вам совет, не надо пытаться "сломать" алгоритм так, что бы он начал выдавать правильный результат.

Согласен.

этот подход будет выдавать неправильный результат при обнаружении нескольких пробелов подряд.

Отличная формулировка. У меня получилось более громоздко и с примером. И пробел в начале.

Теперь вы даёте хорошие, годные (проклятый луркмоар) советы. От комментариев не отписываюсь, но передаю руль вам. Судя по всему немного дожать осталось ). Только пожалуйста не пишите готовое решение, это же ничему не научит.

Да, блок-схема сейчас по-моему это overkill.

Насчёт скипа и '\n' в конце: ну я бы во 2-м while проверку на него (знаю, что 2-й раз) написал. По-моему всё-таки лучше чем ветки. Тем более что if-ы начинаются в 3-й главе.

URL

14.04.2010 в 16:34

Jariad

Либо делать инициализацию "i" да начала вхождения в цикл, либо писать отдельное условие на "больше одного пробела"? Либо полностью перестраивать алгоритм?

URL


Запомнить

ru_programming