Часовой пояс: UTC + 3 часа




Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 28 • Страница 1 из 21  2  >
  Пред. тема | След. тема 
В случае проблем с отображением форума, отключите блокировщик рекламы
Автор Сообщение
 

Member
Статус: Не в сети
Регистрация: 17.11.2003
Откуда: Петроской
в Паскале, это у нас в одной задачке было на вступительных в универ
то есть,
например есть
Код:
readn(a);
readln(b);
IF A>B THEN WRITELN('A>B)
           ELSE WRITELN('B>A')

надо как-то линейно сделать :hitrost:



Партнер
 

Junior
Статус: Не в сети
Регистрация: 12.07.2005
Откуда: Москва
ИМХО это невозможно. Если существуют 2 варианта действий программы, значит алгоритм разветвляется. Попробуй изобразить блок-схему так, чтобы она не ветвилась. Мне слабо :fingal:
Может они имели в виду case of?


 

Member
Статус: Не в сети
Регистрация: 17.11.2003
Откуда: Петроской
вот как было, дается задача про производительность труда. Рабочие выполняют за час N деталей. и Дана норма M в день выполнения, надо узнать, смогут ли рабочие выполнить работу, если дается M и N. Результатом выполнения должен быть либо "Выполнят" либо "Не выполнят". Решить задачу с использованием линейного алгоритма.
дык я показал преподу через IF THEN ELSE, а он говорит, что можно сделать линейно, но вот секрет не стал расскрывать, [censored] :)


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Код:
var A: array [0..1] of String[32];

var B: Boolean;
var X: Integer;

A[0] := "Не выполнят";
A[1] := "Выполнят";

readln(M);
readln(N);

B := N*8 >= M;

X := Ord(B);

writeln(A[X]);


:D

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 17.11.2003
Откуда: Петроской
Anoss йехх... а как понять, словесно объясни плиз
Код:
B := N*8 >= M;

:oops:


 

Member
Статус: Не в сети
Регистрация: 16.07.2006
maslyak писал(а):
Anoss йехх... а как понять, словесно объясни плиз
Код:
B := N*8 >= M;

:oops:

Бэ присвоить - Эн умножить на 8 (к чему это???) - больше либо равно Эм.


 

Member
Статус: Не в сети
Регистрация: 04.06.2005
Откуда: Оксфордшир
8 часов рабочего дня :)

Кстати довольно красиво
Насколько я понял линейное решение должно быть более эффективным? Кто нибудь может проверить на 10000 цикле?


Последний раз редактировалось Alecmg 01.08.2006 21:29, всего редактировалось 1 раз.

 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Ага, 8 часов рабочего дня)
Если у ваших рабочих рабочий день ненормированный, модифицируйте программу сами ))

если (N*8 >= M), то в B окажется "True", а Ord(True) равно 1 :)
Добавлено спустя 35 секунд
B := (N*8 >= M); — так нагляднее :)

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 16.07.2006
А что "X" делает в выводе, в процессе эта переменная не учавствовала, да и никаких значений не принимала???


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Alecmg
Я могу проверить, только чур не на паскале.
Добавлено спустя 1 минуту, 48 секунд
-=DIN=- Внимательнее, X := Ord(B);

Исключительно для наглядности. Я ведь мог написать

Код:
var A: array [0..1] of String[32];

A[0] := "Не выполнят";
A[1] := "Выполнят";

readln(M);
readln(N);

writeln(A[Ord(N*8 >= M)]);

Добавлено спустя 11 минут, 27 секунд
Проверил на 10 000 000 цикле, результаты неоднозначные, но обычно линейный вариант медленнее...

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 16.07.2006
Anoss
Таксс, подзабыл я, что выполняет оператор "Ord" :oops: ?


 

Member
Статус: Не в сети
Регистрация: 04.06.2005
Откуда: Оксфордшир
-=DIN=- писал(а):
Таксс, подзабыл я, что выполняет оператор "Ord"?
boolean преобразует в 1 или 0 я думаю

На Perl в пределе своих способностей проверил, линейный вариант в самом деле медленнее ~ 10%


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Строго говоря, Ord(X) возвращает целочисленное представление X.
Сводится это к тому, что если X — Char, то возвращается его ASCII-код, если X — Boolean, то возвращается 1 для True и 0 для False, и если X — пользовательский перечислимый тип, то возвращается порядковый номер значения :)
т.е.
Код:

var x: Char;
x:='A';
writeln(Ord(x)); — имеем 65
________________________
var x: Boolean;
x:=True;
writeln(Ord(x)); — имеем 1
________________________

type DaysOfTheWeek= (Sun,Mon,Tue,Wed,Thu,Fri,Sat);
var  x : DaysOfTheWeek;
x:=Tue;
writeln(Ord(x)); — имеем 2 (Sun — 0, Mon — 1 и т.д.)

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 16.07.2006
Alecmg
1 -True, 0 - False?


 

Member
Статус: Не в сети
Регистрация: 04.06.2005
Откуда: Оксфордшир
-=DIN=- писал(а):
Alecmg
1 -True, 0 - False?
ну да

Anoss: Ты на чем проверял? 100 000 000 циклов при N random на Perl считалось 86 секунд в среднем - линейно, 74 секунды - if вариант

Просто интересно быстродествие сравнить с компилируемым языком.


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Alecmg На си) Посчитать 100 млн циклов на чистом си? Дай тогда свой код, чтобы было максимально похоже) У меня было 10 млн циклов, N и M — random(10)

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 04.06.2005
Откуда: Оксфордшир
Anoss писал(а):
Alecmg На си) Посчитать 100 млн циклов на чистом си? Дай тогда свой код, чтобы было максимально похоже) У меня было 10 млн циклов, N и M — random(10)

Код:
#!/usr/bin/perl
use strict;
use warnings;

my $m = 24.0; # norm
my $a = 0; # answer counter
my $n; # speed

my @timeData = localtime(time);
print join(' ', @timeData)."\n"; # timestamp start

for (my $c = 0; $c < 1e8; $c++) {
  $n = rand(12); #
  if ($n*8 <= $m) {
    $a++;
  }
}
print "$a\n";
@timeData = localtime(time);
print join(' ', @timeData)."\n"; # timestamp end


Код:
#!/usr/bin/perl
use strict;
use warnings;

my $m = 24.0; # norm
my $a = 0; # answer counter
my $n; # speed

my @timeData = localtime(time);
print join(' ', @timeData)."\n"; # timestamp

for (my $c = 0; $c < 1e8; $c++) {
  $n = rand(12);
  $a += ($n*8 <= $m);
}

print "$a\n"; #answer
@timeData = localtime(time);
print join(' ', @timeData)."\n"; # timestamp end


M=24 и N=rand(12) выбрал от фонаря. 8-часовой рабочий день остался. Переменная $a просто фиксирует сколько раз рабочие выполнили норму.
Ну и для себя поставил выводить время в начале и конце, чтоб замерять можно было.

Athlon 64 2.4GHz 512L2, 1GB DDR@218, всякая дрянь на фоне работает, памяти перл использовал 2 МБ

Последние результаты, когда код подправил и откомментировал
68 линейно и 64 нелинейно.

Edit: Если убрать умножение на 8, а М=3 тот же результат получается за 57 и 52 секунды соответственно. Это я пытаюсь убрать всё постороннее


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Дословный перевод на Си:

Код:
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

//---------------------------------------------------------------------------

int main()
{
   int m = 24; // norm
   int a = 0; // answer counter
   int n; // speed

   int t1, t2; //timestamps

   t1 = GetTickCount();
   
   for (int c = 0; c < 1e8; c++) {
      n = random(12);
      if (n*8 <= m) {
         a++;
      }
   }

   t2 = GetTickCount();
   printf("non-linear: a = %u; %.3f s\n",a,(t2-t1)/1000.);


   a = 0;

   t1 = GetTickCount();

   for (int c = 0; c < 1e8; c++) {
      n = random(12);
     a += (n*8 <= m);
   }

   t2 = GetTickCount();
   printf("linear: a = %u; %.3f s\n",a,(t2-t1)/1000.);

   return 0;
}

(Умножение не убрано)

И один из результатов на профильной системе (сильно колеблется, но соотношение сохраняется):

Код:
non-linear: a = 33335331; 3.828 s
linear: a = 33329534; 3.172 s

Добавлено спустя 4 минуты, 7 секунд
Под «сильно» я имею в виду нелинейный даёт 3.5-4.5 где-то, фигни много фоном..

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


 

Member
Статус: Не в сети
Регистрация: 04.06.2005
Откуда: Оксфордшир
мда, на си циклы быстрее крутятся.

Интересно почему random у нас разные результаты дал?

А чтобы более достоверные результаты получить, сделай 1е9 или 2е9 циклов :)
И ещё: от перестановки мест результат не изменится? Если сначала выполнить линейный код

_________________
Таких людей уже нет, а скоро совсем не будет
BTEAM_Shifty


 

Member
Статус: Не в сети
Регистрация: 01.04.2005
Откуда: Москва-Лубянка
Alecmg А у тебя рандом 25 млн дал?

Я остановил F@H :D

Получил довольно стабильные результаты — линейный 2.6, нелинейный — 2.9, в любом порядке.
Добавлено спустя 1 минуту, 35 секунд
Линейный быстрее, обрати внимание))
Добавлено спустя 6 минут, 59 секунд
По поводу рандома — у меня всё логично, меньше или равны трём четыре значения — {0,1,2,3}, это треть от тех двенадцати, которые дает рандом.
Добавлено спустя 4 минуты, 24 секунды
Кстати, уборка умножения не даёт на 1e8 результата, который можно было бы заметить..

_________________
AnossovPavel в проекте F@H (TSC!Russia)
退屈な祖父 ¤ παππούς ¤ («клан дедов»)


Показать сообщения за:  Поле сортировки  
Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 28 • Страница 1 из 21  2  >
-

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB | Kolobok smiles © Aiwan