ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / еще одна задача по прогаммированию
25 сообщений из 63, страница 2 из 3
  2  все
еще одна задача по прогаммированию
    #35019891
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
0bsidвместо BITS мог бы написать (1<<i) и убрать массив BITS
Мог бы. Только не хотел.
...
Рейтинг: 0 / 0
19.12.2007, 12:13
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020333
MAPA3OT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MAPA3OT
Участник
господа, хоть режьте меня, хоть бейте
но вот это вот:
Код: plaintext
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.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
	    byte[] BITS = new byte[] {
             1 ,  2 ,  4 ,  8 ,  16 ,  32 ,  64 , (byte)  128 };
	    byte sum =  0 ;
	    Random r = new Random();
	    byte[] bytes=new byte[ 10000000 ];
	    for (int i= 0 ;i<bytes.length;i++)
	    {
	    	bytes[i]=(byte)r.nextInt( 256 );
	    }

	    int byteLength=bytes.length;
	    for (int i= 0 ;i<byteLength;i++)
	    {
	    	bytes[i]=(byte)r.nextInt( 256 );
	    }

	    long time1=new Date().getTime();
	    for (int j= 0 ;j<byteLength;j++)
	    {
 
	    	sum= 0 ;
	    	byte b=bytes[j];
			for (int i =  0 ; i < BITS.length; i++) {
			sum += (b & BITS[i]) ==  0  ?  0  :  1 ;
			}
	    }
		
	    System.out.println(new Date().getTime()-time1);
		
	    long time2=new Date().getTime();
	    for (int j= 0 ;j<byteLength;j++)
	    {
	    	sum= 0 ;
	    	byte b=bytes[j];
			while (b> 0 )
			{
				if (b% 2 == 0 )sum++;
				b=(byte)(b/ 2 );
			}
	    }
		
	    System.out.println(new Date().getTime()-time2);

        long time3=new Date().getTime();
	    for (int j= 0 ;j<byteLength;j++)
	    {
	    	sum= 0 ;
	    	byte b=bytes[j];
			while (b> 0 )
			{
				sum=(byte)(sum+b% 2 );
				b=(byte)(b/ 2 );
			}
	    }
		
	    System.out.println(new Date().getTime()-time3);
Говорит, что
1-ый кусок кода выполняется за 984 мс,
2-ой за 485 мс
3-ий за 375 мс
, вот такая вот загогулина.
...
Рейтинг: 0 / 0
19.12.2007, 14:05
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020379
MAPA3OT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MAPA3OT
Участник
если же в первом варианте алгоритма, мы меняем проверку по массиву, на
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
for (int j= 0 ;j<byteLength;j++)
	    {
 
	    	sum= 0 ;
	    	byte b=bytes[j];
			for (int i =  0 ; i <  8 ; i++) {
			sum += ((b>>i)& 1 );
			}
	    }
то время будет - 360
...
Рейтинг: 0 / 0
19.12.2007, 14:16
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020388
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
Код: plaintext
1.
2.
3.
 359 
 422 
 219

Возвращает 0. Как это работает?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
sum =  0 ;
         byte  b = ( byte )  255 ;
         while  (b >  0 ) {
            sum = ( byte ) (sum + b %  2 );
            b = ( byte ) (b /  2 );
        }
        System.out.println("sum = " + sum);
...
Рейтинг: 0 / 0
19.12.2007, 14:18
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020392
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
MAPA3OTесли же в первом варианте алгоритма, мы меняем проверку по массиву...
Код: plaintext
1.
2.
3.
4.
 218 
 375 
 422 
 219

Значит мое предположение об интеллектуальности компилятора Java не оправдалось.
...
Рейтинг: 0 / 0
19.12.2007, 14:20
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020398
MAPA3OT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MAPA3OT
Участник
тэк-с, удалось еще чуть-чуть сократить время
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
 for (int j= 0 ;j<byteLength;j++)
	    {
 
	    	sum= 0 ;
	    	byte b=bytes[j];
			for (int i =  0 ; (b>>i)> 0 ; i++) {
			sum += ((b>>i)& 1 );
			}
	    }
...
Рейтинг: 0 / 0
19.12.2007, 14:21
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020412
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
MAPA3OTтэк-с, удалось еще чуть-чуть сократить время
Займись чем-нибудь полезным :)
...
Рейтинг: 0 / 0
19.12.2007, 14:25
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35020460
MAPA3OT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MAPA3OT
Участник
работает нормально, только не правильно :)
Кстати, второй вариант тоже косячный :(
...
Рейтинг: 0 / 0
19.12.2007, 14:33
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35022940
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
:(Странно, мой код сказал, что таких комбинаций нет :(
Скорее всего можно использовать не только +, но и - :

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
module Main where
 
solve []     n = []
solve (d:ds) n = map ((show n ++ "=")++) (solve' d ds n)
    where
        solve' cur []     n | cur == n = [show cur]   
        solve' cur (d:ds) n = solve' (cur*10+d) ds n
                              ++ (map ((show cur ++ "+")++) (solve' d ds (n-cur)))  
                              ++ (map ((show cur ++ "-")++) (solve' d ds (n+cur)))  
        solve' _   _      _ = []   
 
main = putStrLn $ unlines $ map show $ filter (not.null) $ map (solve [1..7]) [90..100]

Фактически решение в 8 строчек :)

Результат:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
["90=1+23+4+5-67","90=1+23-45+67","90=1-23+4-5+67"]
["91=123+45-6+7","91=12+3+4+5+67","91=1+23+4+56+7"]
["92=1+23+4-5+67"]
["93=1-2-34+5-67"]
["94=12-34+5+67","94=1-2-34+56+7"]
["95=1+2-34+5-67"]
["96=1+2-34+56+7"]
["97=12-3-45+67","97=1-2+34+5-67"]
["98=1-23+4+5+67","98=1-2+34+56+7"]
 ["99=1+2+34+5-67"] 
["100=1+23+4+5+67","100=1+2+34+56+7"]
...
Рейтинг: 0 / 0
20.12.2007, 12:43
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35022955
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
NotGonnaGetUs
"99=1+2+34+5-67"
калькулятор утверждает, что это выражение = -25 (((
...
Рейтинг: 0 / 0
20.12.2007, 12:46
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35022974
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
egorych NotGonnaGetUs
"99=1+2+34+5-67"
калькулятор утверждает, что это выражение = -25 (((

Есть такое. Багс :)
...
Рейтинг: 0 / 0
20.12.2007, 12:49
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35023085
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
egorych NotGonnaGetUs
"99=1+2+34+5-67"
калькулятор утверждает, что это выражение = -25 (((

Тоже самое без багов:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
module Main where
 
solve []     n = []
solve (d:ds) n = map ((show n ++ "=")++) (solve' (+) 0 d ds) 
    where
        solve' f acc cur []     | f acc cur == n = [show cur]   
        solve' f acc cur (d:ds) = solve' f acc (cur*10+d) ds
                              ++ (map ((show cur++"+")++) (solve' (+) (f acc cur) d ds))  
                              ++ (map ((show cur++"-")++) (solve' (-) (f acc cur) d ds))  
        solve' _ _   _   _ = []   
 
main = putStrLn $ unlines $ map show $ filter (not.null) $ map (solve [1..7]) [90..100]

Результат:

Код: plaintext
1.
2.
3.
4.
5.
6.
["90=1+23+4-5+67","90=1-23+45+67"]
["91=123-45+6+7","91=12+3+4+5+67","91=1+23+4+56+7"]
["92=1+23-4+5+67"]
["95=12+34+56-7","95=1-2+34-5+67"]
["96=1-2+34+56+7"]
 ["99=1+2+34-5+67"] 
["100=1+23+4+5+67","100=1+2+34+56+7"]
...
Рейтинг: 0 / 0
20.12.2007, 13:13
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024588
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
NotGonnaGetUs
Код: plaintext
module Main where
А это на чем, простите?
...
Рейтинг: 0 / 0
20.12.2007, 19:01
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024622
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
White Owl NotGonnaGetUs
Код: plaintext
module Main where
А это на чем, простите?
На чем-то лиспоподобном.
Медленное, тормознутое, для реальных задач неприменимое, но вот поиграться — отличная штука.
...
Рейтинг: 0 / 0
20.12.2007, 19:13
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024780
Егорище85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Егорище85
Участник
White Owl NotGonnaGetUs
Код: plaintext
module Main where
А это на чем, простите?

Очень похоже на Хаскелл. Но, мне кажется, решение неправильное, т.к. перестановки цифр не учитываются...
...
Рейтинг: 0 / 0
20.12.2007, 20:59
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024866
Егорище85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Егорище85
Участник
Да, задача конечно тупая - нужно фактически все перестановки и все склейки рассмотреть. Для 99 у меня решения нет. А вот для 100 - 8352 варианта.

Время расчета - 5 секунд (правда на бесплатном учебном компиляторе )

Реализация, разумеется, на самом лучшем языке программирования - Лиспе (диалект - Scheme).

Код не очень красивый, но и алгоритм не строгий с точки зрения математики... Перебор дурацкий ведь...

Код: plaintext
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.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
(define (split-one items)
        (if (null? (cdr items)) items 
                                (list (car items) (cdr items))
        )
)

(define (split-two items)
        (if (null? (cdr items)) ()
                                (if (null? (cdr (cdr items))) (list (+ (* (car items)  10 ) (car (cdr items))))
                                                              (list (+ (* (car items)  10 )
                                                                       (car (cdr items))
                                                                    )
                                                                    (cdr (cdr items))
                                                              )
                                )
        )
)

(define (split-one-iteration items)
        (define (iter-split result elems)
                (if (null? elems) result
                    (if (not (pair? (car elems))) (iter-split (append result (list (car elems))) (cdr elems))
                                                  (let ((car-elems (car elems))
                                                       )                                                     
                                                       (if (null? (split-two car-elems)) (append result (split-one car-elems))
                                                                                         (list (append result (split-one car-elems))
                                                                                               (append result (split-two car-elems))
                                                                                         )
                                                       )
                                                  )
                    )
                )
        )
        (if (null? items) items
                          (iter-split () items)                
        )
)

(define (split items)
        (if (simple-list? items) (list items)
                                 (if (have-pairs? items) (flatmap (lambda (x) (if (simple-list? x) (list x) 
                                                                                                   (split (split-one-iteration x))
                                                                                                    
                                                                              )
                                                                  )
                                                                  items
                                                         )
                                  )
        )
)

(define (task digits require-sum)
        (if (null? digits) ()
                           (filter (lambda (x) (= (accumulate +  0  x) require-sum))
                                   (split (flatmap (lambda (x)
                                                           (list (split-one x) (split-two x)
                                                           )
                                                   ) 
                                                   (permutations digits)
                                          )
                                   )
                           )
        )
)

Результат выполнения:
Код: plaintext
(task (list  1   2   3   4   5   6   7 )  100 )
здесь
...
Рейтинг: 0 / 0
20.12.2007, 22:36
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024926
:(
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
:(
Гость
Егорище85
Время расчета - 5 секунд (правда на бесплатном учебном компиляторе )
На тормознутой джаве эта задача занимает неощутимые доли миллисекунды.
Лисп решает, ясен перец.
...
Рейтинг: 0 / 0
20.12.2007, 23:26
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35024953
Егорище85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Егорище85
Участник
:( Егорище85
Время расчета - 5 секунд (правда на бесплатном учебном компиляторе )
На тормознутой джаве эта задача занимает неощутимые доли миллисекунды.
Лисп решает, ясен перец.

Ну да, такие задачи конечно же очень часто встречаются.

Лисп имеет сильную привязку к математике, конкретно к лямбда-исчислению, поэтому задачи полного перебора для него неестественны.

Если хотите, чтобы быстро работало - берите голый С и высчитывайте мили- и микросекунды...
...
Рейтинг: 0 / 0
20.12.2007, 23:52
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35025371
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
:( White Owl NotGonnaGetUs
Код: plaintext
module Main where
А это на чем, простите?
На чем-то лиспоподобном.
Медленное, тормознутое, для реальных задач неприменимое, но вот поиграться — отличная штука.

Напрасно так думаете. Всего раз в 8 медленнее, чем java %)

Егорище85
Очень похоже на Хаскелл. Но, мне кажется, решение неправильное, т.к. перестановки цифр не учитываются...


Он самый. При желании, можно расширить задачу расстановкой скобок :)
...
Рейтинг: 0 / 0
21.12.2007, 10:07
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35025439
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
NotGonnaGetUsПри желании, можно расширить задачу расстановкой скобок :) для сложения/вычитания расстановка скобок ни помочь, ни помешать не может
...
Рейтинг: 0 / 0
21.12.2007, 10:27
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35025500
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
egorych NotGonnaGetUsПри желании, можно расширить задачу расстановкой скобок :) для сложения/вычитания расстановка скобок ни помочь, ни помешать не может

Ну мы же не в первом классе. Добавим возможность использовать * и / :)
...
Рейтинг: 0 / 0
21.12.2007, 10:37
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35026121
Егорище85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Егорище85
Участник
NotGonnaGetUsОн самый. При желании, можно расширить задачу расстановкой скобок :)

Приятно увидеть любителя функциональных языков. Давно с хаскеллом играетесь?
Используете его для реальных задач?
...
Рейтинг: 0 / 0
21.12.2007, 13:18
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35026137
Егорище85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Егорище85
Участник
NotGonnaGetUsНапрасно так думаете. Всего раз в 8 медленнее, чем java %)

А что за компилятор использовали? Hugs 98?
Дело ведь наверно не только в самом языке...

Кстати у меня работает так долго потому что алгоритм самый дубовый был выбран - все перестановки, а это 7! а потом все возможные парные склейки подряд (без изменения порядка), а это еще около 2^7.

Наверно можно как-то хитрее задачу решить...
...
Рейтинг: 0 / 0
21.12.2007, 13:22
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35026275
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
1) Мысль дурацкая шевельнулась, что надо-де BCD-арифметику использовать. Пока обосновать не могу... Внутренний голос советует

2) Есть один сайтец, где подобные задачки (проблемы) решают каждый день, да еще и конкурсы устраивают. Как-бишь его... Забыл...

3) Эх... нету Ксенофонта...
...
Рейтинг: 0 / 0
21.12.2007, 13:54
| Ответить | Цитировать | Написать  
еще одна задача по прогаммированию
    #35026767
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
Егорище85 NotGonnaGetUsНапрасно так думаете. Всего раз в 8 медленнее, чем java %)

А что за компилятор использовали? Hugs 98?
Дело ведь наверно не только в самом языке...

Кстати у меня работает так долго потому что алгоритм самый дубовый был выбран - все перестановки, а это 7! а потом все возможные парные склейки подряд (без изменения порядка), а это еще около 2^7.

Наверно можно как-то хитрее задачу решить...

ghc.

Сделал твой алгоритм на haskell (чтобы сравнить лаконичность кода и время работы одного и того же дубового алгоритма):

Код: plaintext
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.
module Main where
 
import Text.Printf
import System.CPUTime
 
--- Solution:
 
permutations :: Eq a => [a] -> [[a]]
permutations []    = [[]]
permutations xs = concat [map (x:) (permutations $ filter (x/=) xs) | x <- xs]
 
splice :: [a] -> [[[a]]]
splice []     = [[]]
splice xs = concat [map (first:) (splice rest) | (first, rest) <- split2 xs]
    where
        split2 xs = map (\n -> splitAt n xs) [1.. length xs]
          
combineInts :: [[Int]] -> [Int]
combineInts [] = []
combineInts xs = foldr (\x r -> makeInt x : r) [] xs
    where
        makeInt = foldl (\n r -> n * 10 + r) 0
 
solve :: [Int] -> Int -> [[Int]]           
solve [] n = []
solve xs n = filter (\e -> n == sum e) $ concatMap ((map combineInts). splice) $ permutations xs
 
--- Run test and show computation time:
 
main = 
    do
        putStrLn "Starting..."
        time $ putStrLn $ unlines $ map show $ solve [1..7] 100
        putStrLn "Done."
    where
        time :: IO t -> IO t
        time a = do
            start <- getCPUTime
            v <- a
            end   <- getCPUTime
            let diff = (fromIntegral (end - start)) / (10^12)
            printf "Computation time: %0.3f sec\n" (diff :: Double)
            return v

Получаются теже 8352 вариантов для 1..7 и 100.
Код: plaintext
1.
Computation time: 1.375 sec

Хаскелл круче лиспа :)
...
Рейтинг: 0 / 0
21.12.2007, 16:03
| Ответить | Цитировать | Написать  
25 сообщений из 63, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / еще одна задача по прогаммированию
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35020392&tid=1345591]:
 0ms
get settings:
 4ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 147ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 35ms
get tp. blocked users:
 1ms
others: 245ms
total:  451ms
созд. / загр.: 451ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]