Ivanovo Linux Users Group - Not logged in
Forum Help Search Login
Previous Next Up Topic Программирование / Прикладное / занимательные задачки (174950 hits)
1 2 Previous Next  
- By Aid Date 21.11.09 17:03 Edited 21.11.09 17:27
народ, а давайте выкладывать сдесь интересные задачки, которые видели, заодно и решения + обсудим всё..языки любые....

итак, йа начну
задание "посчитать максимальное кол-во идущий подряд пробелов в строке"
вот решение от меня на java

class Prob
{
  public static void main(String[] args)
  {
    String str="aaa aaaa     bfc   ";
    System.out.println(maxProb(str));
  }
 
  public static int maxProb(String str)
  {
    int[] res=new int[100];
    char[] mas=new char[10];
    mas=str.toCharArray();
   
    //забьём  в res нули
    for(int i=0; i<res.length ; i++)
    {
      res=0;
    }
   
    //зафиксируем значения с пробелами
    int j=0;
    for(int i=0; i<mas.length ; i++)
    {
      if(mas == ' ')
      {
        res[j]++;
      }
      else
      {
        j++;
      }
    }
   
    //найдём максимальное в массиве
    int max=0;
    for(int i=0; i<res.length; i++)
    {
      if(res[max] < res) max=i;
    }
   
    return(res[max]);
  }
}
Memento mortis!!!!
Parent - By Aid Date 21.11.09 17:06 Edited 21.11.09 17:28
сразу же вторая, вывод простых чисел, опять джава

class ProstNum
{
  public static void main(String[] args)
  {
    int t[]=new int[1000];
    t=getArrayNum(10);
   
    for(int x:t)
    {
      if(x==0) continue;
      System.out.println(x);
    }
  }
 
  public static int[] getArrayNum(int max)
  {
    int[] res=new int[10000];
    int k=0;
    for(int i=2; i <= max ; i++)
    {
      for(int j=2; j <= i ; j++)
      {
        if(j == i)
        {
          res[k]=i;
          k++;
        }
        if((i%j) == 0) break;
      }
    }
    return(res);
  }
}
Memento mortis!!!!
Parent By LOE (Site/forum admin) Date 21.11.09 17:51 Edited 21.11.09 18:09
В твоем алгоритме, для каждого числа производится проверка, не делится ли оно на все предыдущие.
Подсчитай, сколько будет итераций циклов и сколько это займет времени.
Вот вариант, использующий метод "решето Эратосфена" (мог бы и погуглить, прежде, чем слету пытаться писать программу ;-) )
$ cat prost_numb.pl                                               
#!/usr/bin/perl                                                   

$N=10000;
$c=0; #для подсчета числа прохода циклов

#заполним все ячейки числами по порядку: 0,1,2,3...
       for($i=0; $i<$N; $i++){
           $a[$i] = $i;
       }
#поскольку 1 не простое число, обнулим ячейку с этим числом
       $a[1]=0;
#выкидываем непростые числа
       for($s=2; $s<$N; $s++){
           if($a[$s]!=0){
               for($j=$s*2; $j<$N; $j+=$s){
                   $c++;
                   $a[$j]=0;
               }
           }
       }
#печатаем результат
       print "число проходов цикла: $c\n";
       for($i=0; $i<$N; $i++){
           if($a[$i]!=0){
                printf("%d\n", $a[$i]);
           }
       }


$ time perl prost_numb.pl > 1.txt

real    0m0.095s
user    0m0.078s
sys     0m0.007s

при этом:
число проходов цикла: 23069
и среди первых 10000 чисел найдено 1229 простых чисел


В аттаче - результат

Attachment: 1.txt (5.8k)
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Aid Date 21.11.09 17:17
есчё одна весёлая, есть множество чисел, получить все подмножества етого множества...у меня есть алгоритм примерный в голове, реализую чуть потом
Memento mortis!!!!
Parent By LOE (Site/forum admin) Date 21.11.09 18:36
Если числа повторяются, считать ли их разными элементами множества или как одно?
Например, дано множество (1 2 1), решением что должно быть? считать ли единички одним элементом или разными?

Просто сама по себе задача - чистая комбинаторика.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By LOE (Site/forum admin) Date 21.11.09 17:32 Edited 24.11.09 23:10
Зачем же все так сложно делать? На кой столько циклов? Зачем что-то там фиксировать и явно задавать размерности временных массивов, если задача стоит в поиске количества.

Максимальное число повторяющихся пробелов в строке:
#!/usr/bin/perl

$S='aaa aaaa     bfc   ';

$max=0;

while($S=~/( +)/g) {
        $max=length($1) if (length($1)>$max);
}

print "max=$max\n";
даст 5

Можно еще проще:
#!/usr/bin/perl

$S='aaa aaaa     bfc   ';
$max=0;

map { $max=length($_) if (length($_)>$max) } ($S=~/( +)/g);
print "max=$max\n";
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Aid Date 21.11.09 17:53
ето да, но йа специально свёл задачу к массивам, так показалось интереснее.....
напиши на перле тогда, чтоб считало в массиве максимальное кол-во подряд идущих элементов
Memento mortis!!!!
Parent - By LOE (Site/forum admin) Date 21.11.09 18:07
Не важно каких? Главное, чтоб одинаковые последовательно?
Например, если массив такой:
a b c c a a a k j j
то должно выдать 3 ?
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Aid Date 21.11.09 18:07
нене, заранее ихвестно каких
Memento mortis!!!!
Parent - By LOE (Site/forum admin) Date 21.11.09 18:11
Т.е. в моем примере при условии, что повторяющиеся элементы - это a ?
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent By Aid Date 21.11.09 18:15
млин, ну вот у меня пробелы были
дан массив и число, найти кол-во макс повторений подряд етого числа
Memento mortis!!!!
Parent By LOE (Site/forum admin) Date 21.11.09 18:27
Вот:
поиск максимального количества подряд идущего заданного числа в массиве чисел:
#!/usr/bin/perl

@M=qw'1 2 1 1 5 7 1 1 1 1 3 3 6 6 6 6 6 6'; # задаем массив чисел
$N=1; #задаем число для поиска

$max=0;
$t=0;

map { if ($_==$N) { $t++ } else { $max=($t>$max)?$t:$max; $t=0; } } @M;
$max=($t>$max)?$t:$max; # предохранитель, если число - последнее в массиве

print "max=$max\n";

на выходе: max=4

По сути - все в одной строке ;-)
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Aid Date 22.11.09 19:38 Edited 22.11.09 21:51
вот йа немного по другому сделал ))

class MaxProb
{
  public static void main(String[] args)
  {
    String str=" aaa   aaa  a";
    System.out.println(getProb(str));
    System.out.println(str.indexOf("bb"));
  }
 
  public static int getProb(String str)
  {
    int res=0;
   
    if(-1 != str.indexOf(" "))
    {
      String t=" ";
      for(int i=2; i<str.length(); i++)
      {
        t=t+" ";
        if(-1 == str.indexOf(t))
        {
          res=i-1;
          break;
        }
      }
    }
    return(res);
  }
}


PS from LOE: оформляй блоки кода в тэги [block] .. [/block]
Memento mortis!!!!
Parent - By LOE (Site/forum admin) Date 22.11.09 21:55
В какой среде ты пишешь на java? Там есть профилировщик?
Попробуй запустить разные варианты раз по 10000 и сравни время исполнения.

Я к чему: не всегда более короткий код исполняется быстрее.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent By Aid Date 23.11.09 14:26
ну ни си-шарп же да)))))
да второй вариант быстрее, там только один цикл)))
Memento mortis!!!!
Parent - By sungreen Date 23.11.09 18:32 Edited 23.11.09 18:36
... на прологе ...
test([],V,M):-append([V],M,M1), max_list(M1,N), write(N).
test([32|T],V,M):- V1 is V + 1, test(T,V1,M).
test([_|T],V,M):- append([V],M,M1), test(T,0,M1).


тест
test("  I      Abc  def   ghk ikl       s", 0, []).
результат ~7
Parent By sungreen Date 24.11.09 04:34
... или без списка ...
test([],V,M):- V>M->write(V);write(M).
test([32|T],V,M):- V1 is V + 1, test(T,V1,M).
test([_|T],V,M):- V>M->test(T,0,V); test(T,0,M).
Parent - By Aid Date 23.11.09 23:50
у кого есчё что-нибудь занимательное есть?
Memento mortis!!!!
Parent By sungreen Date 24.11.09 04:35

>> у кого есчё что-нибудь занимательное есть?


... для кодера или так по жизни? ...
Parent - By Bercut Date 24.11.09 07:24
я в свое время, для изучения возможностей перла, реализовал задачу под назанием магические квадраты.
суть задачи следующая. имеется квандрат разделенный на 3 столбца и 3 строки, как в крестики нолики, как поэт пишу стихами.
дык вот его надо заполнить цыферами от 1 до 9 так чтобы сумма по строкам по столбцам и по диагоналям была одинаковой.

код правда я про...терял, как и большинство поступают с учебными материалами, но могу автритетно заявить, что конечный вариант решения был не более 10 строк при нормальном оформлении кода.
кто превзойдет мой результат, томууу ....... ниче не дам, как и остальным в прочем... ;-)
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By sungreen Date 24.11.09 07:57
... кста, вот почемуто уверен что задача с количеством пробелов между словами (самая первая) должна Перле решаться в одно действие, не так ли? ...
... а, магический квадраты, это как раз для Пролога видимо ...
Parent By Aid Date 24.11.09 14:16
да не, с регулярными выражениями в любом будет впринципи просто
Memento mortis!!!!
Parent - By LOE (Site/forum admin) Date 24.11.09 23:11
дык
см этот пост
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent By sungreen Date 25.11.09 08:15 Edited 25.11.09 08:23
... ага, совершенно верно, именно так ...
... и как цель - не просто решить замечательную задачку, а предложить инструмент для решения, оценить красоту кода ...
Parent - By sungreen Date 26.11.09 17:48
... магические квадраты на Прологе ...

% вот предекаты
ts(_,_,[]).
ts(N,M,[H|T]):-member(H,M), delete(M,H,M1), ts(H,M1,T), N\=H.
ss(A,N1,N2,N3,S):-nth(N1,A,V1),nth(N2,A,V2),nth(N3,A,V3), S is V1+V2+V3.

% а вот и вопрос
  append([],[_,_,_,_,_,_,_,_,_],A),
  ts(0,[1,2,3,4,5,6,7,8,9],A),
  ss(A,1,2,3,S),ss(A,4,5,6,S),ss(A,7,8,9,S),
  ss(A,1,4,7,S),ss(A,2,5,8,S),ss(A,3,6,9,S),
  ss(A,1,5,9,S),ss(A,3,5,7,S),
  write(A),
        write(S).
%
A = 2,7,6,
    9,5,1,
    4,3,8

S = 15
Parent - By sungreen Date 26.11.09 19:41
... вариант 2 ...

% собственно предикаты практически не изменились
ts(_,_,[]).                                                      % ну если список2 пуст, то и делать нечего
ts(N,M,[H|T]):-member(H,M), delete(M,H,M1), ts(H,M1,T), N\=H.    % взять значение для головы списка2 из списка1
ss(A,B,C,S):- S is A+B+C.                                        % ну эт просто сумма

% опять же как задать вопрос
ts(0,[1,2,3,4,5,6,7,8,9],[X1,X2,X3,X4,X5,X6,X7,X8,X9]),         %заполнить список2 значениями из списка1
ss(X1,X2,X3,S),ss(X4,X5,X6,S),ss(X7,X8,X9,S),                  
ss(X1,X4,X7,S),ss(X2,X5,X8,S),ss(X3,X6,X9,S),
ss(X1,X5,X9,S),ss(X3,X5,X7,S).
Parent - By Bercut Date 27.11.09 07:01
однако элегантно
пойду учить пролог
но, как же без но то...
решений насколько я помню то ли 3 то ли 5, почему одно
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By sungreen Date 27.11.09 07:14 Edited 27.11.09 07:19
... ты прав, ты прав, их больше ...
... но суть  - как правильно задать вопрос ...
... чтобы найти оставшиеся решения нужно после последней точки добавить всего одно слово fail ...
... то есть предикаты описывают нашу модель, а вопрос задать можно любой ...

...  write(A),write(S),fail.
или
... ss(X1,X5,X9,S),ss(X3,X5,X7,S),fail.
Parent By Bercut Date 27.11.09 07:34
круть
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent By LOE (Site/forum admin) Date 28.11.09 17:08
В связи с полным игнорированием просьбы не писать точки в начале и конце строк, выношу официальное кю sungreen'у.
Пришлось заскриптовать отработку точек, что может повлечь неудобства для обычных пользователей.


PS. значение слова кю расшифровано в фильме "Кин-Дза-Дза" или в википедии
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By LOE (Site/forum admin) Date 27.11.09 07:44
Выношу уже публично:
прошу (навязчиво):
А) не использовать точки в начале и конце каждой строки;
Б) цитируемый код обрамлять тэгами: [block] ... [/block]

PS. читающих твои сообщения тоже надо уважать.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By hawk Date 27.11.09 08:03
Для цитирования вроде

>> знаки


А нельзя кнопку block добавить в ответ? Довольно часто используемая кнопка, намного полезнее скажем той же tt
echo "good..." | perl -e '$??s:;s:s;;$?::s;;=]=>%-{<-|}<&|`{;;y; -/:-@[-`{-};`-{/" -;;s;;$_;see'
Parent - By LOE (Site/forum admin) Date 27.11.09 09:08
Кнопку block сделал.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent By hawk Date 27.11.09 09:09
Спасибо!
echo "good..." | perl -e '$??s:;s:s;;$?::s;;=]=>%-{<-|}<&|`{;;y; -/:-@[-`{-};`-{/" -;;s;;$_;see'
Parent - By Bercut Date 27.11.09 09:57
а точки чем не нравятся?
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By LOE (Site/forum admin) Date 27.11.09 10:18
Коротко: всем.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Bercut Date 27.11.09 11:25
тоталитаризьм и диктатура
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By LOE (Site/forum admin) Date 27.11.09 11:38
Элементарно: уважение к тем, кто будет тебя читать.
Но это выходит за рамки топика и с обсуждением вопроса оформления надо завязывать.
Если что - приват или топик в другом разделе.
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent By Bercut Date 27.11.09 11:46
ок
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By slam Date 03.02.10 09:35
Нужно заменить ровно один (любой) символ в следующей строке, причём так, чтобы она скомпилилась и было выведено ровно 20 звёздочек:

int main() { int i, n = 20; for (i = 0; i < n; i--) { printf("*"); } }

есть три решения, первое я сам нашел, на остальные сдался и подглядел подсказки.
Parent - By sungreen Date 03.02.10 15:11
знаю два
Parent - By sungreen Date 03.02.10 16:18
три
Parent - By Bercut Date 04.02.10 12:03
вещай
а то я тока два нашел
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By slam Date 04.02.10 12:39
int main() { int i, n = 20; for (i = 0; i < n; n--) { printf("*"); } }
int main() { int i, n = 20; for (i = 0; -i < n; i--) { printf("*"); } }
int main() { int i, n = 20; for (i = 0; i + n; i--) { printf("*"); } }
Parent - By Bercut Date 04.02.10 13:35
второе решение не замена символа а добавление
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By slam Date 04.02.10 14:04
Ну да... Замена плюса на минус, но если смотреть в сторону символов, то да, получается что добавление.
Parent By Bercut Date 04.02.10 14:28
вроде как суть задачи в этом
что именно один символ на другой

да
еще бы блин сформулировали чтоб контрольная сумма не изменилась
вот тогда бы померились умением писать полиморфы ;-)
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By LOE (Site/forum admin) Date 04.02.10 14:06
Замена пробела на минус.
под условие подходит ;-)
"No! Try not! Do. Or do not. There is no try." -- Yoda
Parent - By Bercut Date 04.02.10 14:25
а где там лишний пробел
а если заменить не лишний то не компильнется
русский язык подобен искуству кун-фу, и великий мастер никогда не применит его без необходимости...
Parent - By sungreen Date 04.02.10 15:02
без #include  <stdio.h> не компильнется
а заменив пробел на минус компильнется
Previous Next Up Topic Программирование / Прикладное / занимательные задачки (174950 hits)
1 2 Previous Next  

Powered by mwForum 2.12.0 © 1999-2007 Markus Wichitill

Page created in 0.113s with 10 database queries.