Подайте заявку, которая определяет, отсортирована ли последовательность чисел - PullRequest
Новая
       31

Подайте заявку, которая определяет, отсортирована ли последовательность чисел

3 голосов
/ 30 января 2011

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

Code-Bowling - это вызов для писать самые неясные, неоптимизированные, ужасный и ублюдочный код возможный. В основном, точный напротив Code-Golf.

Задача :

Создайте программу, которая берет последовательность чисел и определяет, находятся ли они в порядке возрастания.

Пример 

$ ./myprogram 1 2 7 10 14
true

$ ./myprogram 7 2 0 1
false

Правила

На самом деле их нет. Это может быть консольное приложение, это может быть веб-страница, это может быть что угодно. Это просто должна быть отдельная программа, которая принимает цифры и возвращает цифры. Формат и методы на 100% зависят от вас.

Так что повеселитесь, и давайте посмотрим на изощренные решения, которые вы можете придумать!

Ответы [ 7 ]

2 голосов
/ 07 февраля 2012

Это использует то, что я называю "Родительская сортировка". Для списка больше, чем размер 1, вы должны спросить маму или папу о каждой паре чисел. Это интересно, потому что есть вероятность, что мама попросит тебя пойти с папой, и есть большая вероятность, что папа попросит тебя спросить маму. Может работать вечно, предполагая бесконечные возможности стека. 

function askMom($num1, $num2) {
    $chance = mt_rand(0,2);
    if ($chance>1) {
        return askDad($num1, $num2);
    } else {
        return $num1 <= $num2;
    }
}
function askDad($num1, $num2) {
    $chance = mt_rand(0,4);
    if ($chance>1) {
        return askMom($num1, $num2);
    } else {
        return $num1 <= $num2;
    }
}

function parentSort(array $numbers) {
    for ($i = 0; $i < count($numbers)-1; $i++) {
        $chance = mt_rand(0,1);
        if ($chance) {
            if (askMom($numbers[$i], $numbers[$i+1])) {

            } else {
                return false;
            }
        } else {
            if (askDad($numbers[$i], $numbers[$i+1])) {

            } else {
                return false;
            }
        }
    }

    return true;
}
1 голос
/ 01 февраля 2011

Вот быстрый.Интересно, что он все равно должен быть довольно эффективным, поскольку он повторяет термины только один раз.Он может работать только с числами от 0 до 255 ... 

array_shift($argv);
$str = str_repeat(chr(0), 256);
foreach ($argv as $key => $element) {
    $str[(int) $element] = chr($key + 1);
}
$str = str_replace(chr(0), '', $str);
$hex = unpack('H*', $str);
for ($i = 1; $i < strlen($str); $i++) {
    if (substr($hex[1], $i * 2 - 2, 2) != dechex($a)) {
        echo "False\n";
        die();
    }
}
echo "True\n";

Он работает путем инвертирования строки (1 2 5 4 становится 1 2 0 4 3, другими словами, число в последовательности становится ключом врезультат, и позиция в последовательности становится значением. Тогда все, что нам нужно проверить, это то, что 1 находится в положении 1.

И в том же духе (та же теория, только теория множествоперации): 

array_shift($argv);
$vals = array_flip($argv);
ksort($vals);
echo array_values($vals) == range(0, count($vals) - 1) ? "True\n" : "False\n";
1 голос
/ 31 января 2011

Это решение имеет производительность O (n!) В худшем случае и работает, генерируя все возможные перестановки списка, а затем вычисляет число (см. Функцию 'value'), которое имеет минимум для последовательных списков (по возрастанию или по убыванию). ). 

def value(list):
    sum = 0
    for i in range(len(list)-1):
        sum = sum + (list[i]-list[i+1])**2.0
    return sum

def drop(lst, i):
     if i + 1 >= len(lst):
         return lst[:i]
     else:
         return lst[:i] + lst[i+1:]

class list_permute:
    def __init__(self, lst):
        self.lst = lst
        self.i = -1
        self.subiter = None
    def __iter__(self):
        return self
    def next(self):
        if len(self.lst) == 1:
            if self.i == -1:
                self.i = self.i + 1
                return self.lst
            else:
                raise StopIteration()

        if self.subiter != None:
            try:
                return [self.lst[self.i]] + self.subiter.next()
            except StopIteration:
                self.subiter = None

        if self.subiter == None:
            self.i = self.i + 1
            if self.i >= len(self.lst):
                raise StopIteration()
            else:
                self.subiter = list_permute(drop(self.lst, self.i))
            return self.next()

def test(list):
    given = value(list)
    for i in list_permute(list):
        if value(i) < given:
            return False

    # Test for false positive
    if list[0] > list[len(list)-1]:
        return False
    return True

list = []
print "Feed me your numbers (end with ^C)"
try:
    while True:
        try:
            list.append(int(raw_input()))
        except ValueError:
            print "NaN"
except (KeyboardInterrupt, EOFError):
    pass

print test(list)
1 голос
/ 31 января 2011 
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv){
    int a, b;
    if (argc > 2){
        sscanf(argv[1], "%d", &a);
        sscanf(argv[2], "%d", &b);
        if (a<=b) 
            return main(argc-1, argv+1);
        printf("false");
        exit(0);
    };
    printf("true");
    return 0;
};
0 голосов
/ 04 мая 2011

Впервые я использовал динамическое программирование, чтобы сделать вещи хуже. Он имеет сложность времени и пространства O (n²) 

    #include <stdio.h>
    int main (int argc, char **argv)
    {
      int is_ordered[1000][1000];
      int list[1000];
      int i,j;

      for(i = 1; i < argc; i++)
        sscanf(argv[i],"%d", &list[i-1]);

      for (i = 0; i < argc -2; i++)
      {
        if (list[i] < list[i+1])
          is_ordered[i][i+1] = 1;
        else
          is_ordered[i][i+1] = 0;
      }

      for (i = 2; i < argc -1; i++)
        for (j = 0; j < (argc - 1 - i); j++)
        {
          if (is_ordered[j+1][i+j] && is_ordered[j][i+j-1])
            is_ordered[j][j+i] = 1;
          else
            is_ordered[j][j+i] = 0;
        }

      if(is_ordered[0][argc-2])
        printf("True\n");
      else
        printf("False\n");
      return 0;
    }
0 голосов
/ 04 февраля 2011

Да, Питон! 

def IsSorted(lst):
    return sorted(lst) == lst
0 голосов
/ 02 февраля 2011

Это решение не без оптимизации, но оно мрачное, ужасающее и ублюдочное ... 

/* Either #define macros FIRST, SECOND, THIRD, etc. here, or do so on the
 * command line when "compiling" i.e.
 * $ gcc -D FIRST=1 -D SECOND=5 -D THIRD=42
 */

#define min(X, Y) ((X) < (Y) ? (X) : (Y))

#define pairsorted(X, Y) (min((X), (Y)) == (X) ? 1 : 0)

#if defined (FIRST) && defined (SECOND) && pairsorted(FIRST, SECOND)
#if defined (THIRD) && pairsorted(SECOND, THIRD)
#if defined (FOURTH) && pairsorted (THIRD, FOURTH)
#if defined (FIFTH) && pairsorted (FOURTH, FIFTH)
#error "Sorted!"
#elif !defined (FIFTH)
#error "Sorted!"
#else /* FIFTH is defined and < FOURTH */
#error "Not sorted!"
#endif /* FIFTH */

#elif !defined (FOURTH)
#error "Sorted!"
#else /* FOURTH is defined and < THIRD */
#error "Not sorted!"
#endif /* FOURTH */

#elif !defined (THIRD)
#error "Sorted!"
#else /* THIRD is defined and < SECOND */
#error "Not sorted!"
#endif /* THIRD */

#elif !defined (SECOND)
#error "Sorted!"
#else /* SECOND is defined and < FIRST */
#error "Not sorted!"
#endif /* SECOND */

#ifndef SECOND
#error "I need at least two values to compare"
#endif

Этот (ab) использует компилятор C в качестве среды выполнения или может быть вызван с помощью следующего сценария оболочки для более красивого вывода (полагается на то, что выше указано в sortedcpp.c): 

#!/bin/bash

ORDINALS=(ZEROTH FIRST SECOND THIRD FOURTH FIFTH)
VALUES=(0 $@)

for i in 1 2 3 4 5; do
  if [ $i -le $# ]
    then
      flags="$flags -D ${ORDINALS[$i]}=${VALUES[$i]}"
  fi
done

output=`gcc $flags sortedcpp.c 2>&1`

echo $output | sed -e 's/sortedcpp.c:[0-9]*: error: #error \"\(.*\)\"/\1/'
...