Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / еще одна задача по прогаммированию / 25 сообщений из 63, страница 1 из 3
  1  все
18.12.2007, 19:18
    #35018781
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
в последнне время как обычно перед сессией увеличилось кол-во постов от учащихся с просьбой решить элементарные задачи по программированию( сложить, умножить матрицы и т.д. )

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

Условиеданы числа 1, 2, 3, 4, 5, 6, 7. Как их сложить, используя все семь, чтобы получилось 99.
Пример сложения: 1+2+3+54+67, 21+34+7+6+5, 1+2+3+4+5+6+7 1+27+3+46 и т.д.

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

и так предлагаю что-то вроде конкурса на самое оптимальное решение:
1. по скорости
2. по количеству строк кода

мой вариант смотрите ниже

-

Цель в жизни определяет все..
Выбор есть всегда..
Но мы часто не хотим его делать..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 19:24
    #35018795
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Код: 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.
64.
65.
66.
#include "stdio.h"

int main(){

    int ish[] = {  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7  };
    int vart[ 100 ] = {  0  };
    int kol =  0 ;
    int obsKolvo =  0 ;

    for ( int i =  0 ; i <  7 ; i++ )
    {

        for ( int j =  0 ; j <  7 ; j++ )
        {
            if ( ish[i] != ish[j] ){
                vart[kol] = ish[i]* 10  + ish[j];
                kol++;
            }

        }
        printf( "\n" );

    }

    printf( "Kol-vo elementov=%i", kol);

    for ( int i =  0 ; i <  7 ; i++ )
    {
        int a = ish[i];

        for ( int j =  0 ; j < kol; j++ )
        {
            if ( a != vart[j]/ 10  && a != vart[j]% 10  &&  a + vart[j] <  99  )
            {
                int b = vart[j];

                for ( int k =  0 ; k < kol; k++ )
                {
                    if ( b != vart[k]/ 10  && b != vart[k]% 10  && a != vart[k]/ 10  && a != vart[k]% 10  && a + b + vart[k] <  99  )
                    {
                        int c = vart[k];

                       for ( int l =  0 ; l < kol; l++ )
                       {
                            int d  = vart[l];
                            if ( a != d/ 10  && a != d% 10  &&  b != d/ 10  && b != d% 10  &&  c != d / 10  && c != d% 10  && a + b + c + d ==  99  )
                            {

                                printf( "res = %i %i %i %i \n", a, b, c, d );
                                obsKolvo++;
                            }

                       }

                    }

                }

            }

        }

    }

    printf( "Obsh Kolvo Variantov=%i", obsKolvo );
    return  0 ;
}

из принципа оптимизации следует ввести проверку числа В : В должно быть меньше 86
так как 1+2+3+4+5 +B(86) >99
-

Цель в жизни определяет все..
Выбор есть всегда..
Но мы часто не хотим его делать..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 19:28
    #35018804
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Код: plaintext
1.
2.
3.
4.
  
...
 if ( b != vart[k]/ 10  && b != vart[k]% 10  && a != vart[k]/ 10  && a != vart[k]% 10  && a + b + vart[k] <  99   && b <  86  )
...
-

Цель в жизни определяет все..
Выбор есть всегда..
Но мы часто не хотим его делать..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 19:54
    #35018840
0bsid
0bsid
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
-Sergey-...
и так предлагаю что-то вроде конкурса на самое оптимальное решение:
1. по скорости
2. по количеству строк кода
...

3. лучше на понятность кода
а то ish, vart и прочая куча вложенных циклов и условий
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:01
    #35018850
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
-Sergey-Как их сложить, используя все семь, чтобы получилось 99.
По-моему, никак. Выходит ноль результатов.

-Sergey-1. по скорости
Лень, честно говоря.

-Sergey-2. по количеству строк кода
Код: 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.
 type 
  TDigit =  1 .. 7 ;
  TDigits =  set   of  TDigit;

 procedure  Calc (Sum, Cur: integer; Trace:  string ; Digits: TDigits);
 var  i: integer;
 begin 
   if  Digits = []  then 
     if  Sum + Cur =  99   then 
      FormCalc.edResult.Lines.Add (Trace + '+' + IntToStr (Cur))
     else 
   else 
     for  i := Low (TDigit)  to  High (TDigit)  do 
       if  i  in  Digits  then 
       begin 
         if  Cur >  0   then  Calc (Sum + Cur, i, Trace + '+' + IntToStr (Cur), Digits - [i]);
        Calc (Sum, Cur *  10  + i, Trace, Digits - [i]);
       end ;
 end ;

 procedure  TFormCalc.btnCalcClick(Sender: TObject);
 begin 
  edResult.Clear;
  Calc ( 0 ,  0 , '', [ 1 .. 7 ]);
 end ;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:05
    #35018860
:(
:(
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Странно, мой код сказал, что таких комбинаций нет :(
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:08
    #35018868
:(
:(
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Код: plaintext
1.
2.
Not found... Iterations =  210 
In  0  msec
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:09
    #35018870
:(
:(
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Тут негде соревноваться по скорости.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:45
    #35018909
0bsid
0bsid
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
я тож не нашёл
64 варианта
самый близкий 1 + 23 + 4 + 5 + 67 = 100
тото он второй день решает
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 20:54
    #35018922
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
-Sergey-мой вариант смотрите ниже
1) мешанина из Си и С++
2) обилие нечитаемых имен переменных
3) возможно считает не правильно. В условии не сказано что можно одну и туже цифру использовать дважды. Впрочем и запрета на это нету, хотя он обычно подразумевается в таких задачах.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 21:04
    #35018932
0bsid
0bsid
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
White Owl..
3) возможно считает не правильно. В условии не сказано что можно одну и туже цифру использовать дважды. Впрочем и запрета на это нету, хотя он обычно подразумевается в таких задачах.
вот блин, я не заметил даже, что их можно переставлять
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 21:05
    #35018933
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
0bsidсамый близкий 1 + 23 + 4 + 5 + 67 = 100
Да, если скорректировать, вариантов полно. Например, без единицы:
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 22:00
    #35018985
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
0bsid softwarer and other
да я действительно не сказал что мой вариант "условно" правильный. :-)
При заданных условиях (не использовать перестановку , использовать цифру только один раз ) толку в нем ноль..

3. читабельность кода(оформление) - это хороший критерий , и
мой код на него не претендует, но учитывать его стоит.

по признаку 2 и 3 наиболее удачным является пример softwarer

-

Цель в жизни определяет все..
Выбор есть всегда..
Но мы часто не хотим его делать..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 22:21
    #35019001
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
если кому-то еще данный топик интересен предлагаю следующую задачку

Условие: написать функцию которая на входе получает байт а на выходе возвращает количество установленных в нем битов, написать несколько вариантов функции :
а) опитимизованный по памяти
б) оптимизированный по скорости


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

-

Цель в жизни определяет все..
Выбор есть всегда..
Но мы часто не хотим его делать..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 22:59
    #35019025
:(
:(
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
-Sergey-
Условие: написать функцию которая на входе получает байт а на выходе возвращает количество установленных в нем битов, написать несколько вариантов функции :
а) опитимизованный по памяти
б) оптимизированный по скорости


данную задачу я прочитал давно на каком-то форуме посвященному поиску работы, и на авторство не предендую.
Возникают сомнения в том, что здесь вообще что-то можно оптимизировать. Алгоритм известен 100 лет и туп как дрова.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2007, 23:21
    #35019040
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Алгоритм - слишком громкое слово Упражнение на знание системы команд.
Для Эльбруса - одна команда - ПЧЕ
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 00:24
    #35019088
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
:( -Sergey-
Условие: написать функцию которая на входе получает байт а на выходе возвращает количество установленных в нем битов, написать несколько вариантов функции :
а) опитимизованный по памяти
б) оптимизированный по скорости


данную задачу я прочитал давно на каком-то форуме посвященному поиску работы, и на авторство не предендую.
Возникают сомнения в том, что здесь вообще что-то можно оптимизировать. Алгоритм известен 100 лет и туп как дрова.

код в студию :-)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 00:28
    #35019092
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
ИзопропилАлгоритм - слишком громкое слово Упражнение на знание системы команд.
Для Эльбруса - одна команда - ПЧЕ
к сожаления с Эльбрусом не знаком, но я не занал что существует стандартное решение данной задачи..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 00:43
    #35019100
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
массив из 256 элементов, содержащтй к-во единиц в байте, используемом как индекс массива - как самое быстрое устроит?
Оптимизированный по памяти - в каких попугаях измерять будем?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 00:48
    #35019103
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
ИзопропилАлгоритм - слишком громкое слово Упражнение на знание системы команд.
Для Эльбруса - одна команда - ПЧЕ
фигасе. какие люди
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 00:52
    #35019105
:(
:(
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Можно смело писать вот так (особенно, когда у нас двухбатовые и более числа).
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
    private final static byte[] BITS = new byte[] {
                                        1 ,  2 ,  4 ,  8 ,  16 ,  32 ,  64 , (byte)  128 };
    public static byte getBytesCount (byte b) {
        byte sum =  0 ;
        for (int i =  0 ; i < BITS.length; i++) {
            sum += (b & BITS[i]) ==  0  ?  0  :  1 ;
        }
        return sum;
    }
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 11:16
    #35019668
0bsid
0bsid
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
:(Можно смело писать вот так (особенно, когда у нас двухбатовые и более числа).
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
    private final static byte[] BITS = new byte[] {
                                        1 ,  2 ,  4 ,  8 ,  16 ,  32 ,  64 , (byte)  128 };
    public static byte getBytesCount (byte b) {
        byte sum =  0 ;
        for (int i =  0 ; i < BITS.length; i++) {
            sum += (b & BITS) ==  0  ?  0  :  1 ;
        }
        return sum;
    }


вместо BITS [i] мог бы написать (1<<i) и убрать массив BITS
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 11:24
    #35019713
-Sergey-
-Sergey-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
ИзопропилОптимизированный по памяти - в каких попугаях измерять будем?
на сколько я помню критерием выступало количество переменных и их размерность -
чем больше количество используемых для вычисления переменных тем менее эфективен код по памяти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 12:01
    #35019838
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
0bsid
вместо BITS мог бы написать (1<<i) и убрать массив BITS

оптимизирующему компилятору - по барабану, он цикл развернёт, а константы -вместо выборки из массива - будет сам сдвигом в регистре формировать.
Код: 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.
?getBytesCount@@YAEE@Z PROC				; getBytesCount, COMDAT
; _b$ = ecx

;  10    :         unsigned char sum =  0 ;
;  11    :         for (int i =  0 ; i <  8 ; i++) {
;  12    :             sum += (b & BITS[i]) ==  0  ?  0  :  1 ;

   00000 	8a c1		 mov	 al, cl
   00002 	c0 e8  06 	 shr	 al,  6 
   00005 	 24   01 		 and	 al,  1 
   00007 	8a d1		 mov	 dl, cl
   00009 	c0 ea  05 	 shr	 dl,  5 
  0000c	 80  e2  01 	 and	 dl,  1 
  0000f	 02  c2		 add	 al, dl
   00011 	8a d1		 mov	 dl, cl
   00013 	c0 ea  04 	 shr	 dl,  4 
   00016 	 80  e2  01 	 and	 dl,  1 
   00019 	 02  c2		 add	 al, dl
  0001b	8a d1		 mov	 dl, cl
  0001d	c0 ea  03 	 shr	 dl,  3 
   00020 	 80  e2  01 	 and	 dl,  1 
   00023 	 02  c2		 add	 al, dl
   00025 	8a d1		 mov	 dl, cl
   00027 	c0 ea  02 	 shr	 dl,  2 
  0002a	 80  e2  01 	 and	 dl,  1 
  0002d	 02  c2		 add	 al, dl
  0002f	8a d1		 mov	 dl, cl
   00031 	d0 ea		 shr	 dl,  1 
   00033 	 80  e2  01 	 and	 dl,  1 
   00036 	 02  c2		 add	 al, dl
   00038 	8a d1		 mov	 dl, cl
  0003a	c0 ea  07 	 shr	 dl,  7 
  0003d	 02  c2		 add	 al, dl
  0003f	 80  e1  01 	 and	 cl,  1 
   00042 	 02  c1		 add	 al, cl

;  13    :         }
;  14    :         return sum;
;  15    :     }
Вопрос остаётся - в каких попугаях будем измерять оптимизацию по памяти?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.12.2007, 12:10
    #35019876
0bsid
0bsid
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
еще одна задача по прогаммированию
Изопропил 0bsid
вместо BITS мог бы написать (1<<i) и убрать массив BITS

оптимизирующему компилятору - по барабану, он цикл развернёт, а константы -вместо выборки из массива - будет сам сдвигом в регистре формировать.

Вопрос остаётся - в каких попугаях будем измерять оптимизацию по памяти?

Код: plaintext
shr	dl,  7
интересно он двигает биты
по идее должно быть shl dl, 1

вообще задача для 7-классника
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / еще одна задача по прогаммированию / 25 сообщений из 63, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 479ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1345591]:
 0ms
get settings:
 9ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 164ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 64ms
get tp. blocked users:
 1ms
others: 218ms
total:  479ms
x
x
Закрыть


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