2006年7月アーカイブ

トップページから移動

これのC++版です。LLじゃないけど
特に変わったことはしてないけど、
h(100000)の計算が約0.3秒ですむという驚異。やはりC++、すばらしい(´▽`ノ
#include <iostream>
#include <algorithm> //max_element
#include <map>
#include <cstdlib> // atoi

typedef std::map<int,int> xs_t;

int g(int n) {
  return ( n == 1 ) ? 1 : 1 + g((n%2) ? n*3+1 : n/2);
}

int s(const xs_t::value_type& lhs, const xs_t::value_type& rhs) {
  return lhs.second < rhs.second;
}

int h(int n) {
  xs_t xs;
  for (int i = 0; i < n; ++i) {
    xs[i+1]=g(i+1);
  }
  return std::max_element(xs.begin(), xs.end(), s)->first;
}

int main(int argc, char** argv) {
  int n = ( argc > 1) ? std::atoi(argv[1]) : 100;
  std::cout << "h(" << n << ")=" << h(n) << std::endl;
  return 0;
}
[追記]
せっかくなのでLL2006の方にトラックバックしておきます :D
Round2はCollatz予想というものらしい. で、早速

#!perl
#

use strict;

sub f;
sub g;
sub h;

use Time::HiRes;

my $t = Time::HiRes::time;
print h(100), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub f {
  my $n = shift;
  if ( $n == 1 ) {
    1;
  }
  elsif ( $n % 2 ) {
    3 * $n + 1;
  }
  else {
    $n / 2;
  }
}

sub g {
  my $n = shift;
  my $cnt;
  do {
    ++$cnt;
  } until ( ($n = f($n)) == 1 );
  ++$cnt;
}

sub h {
  my $n = shift;

  my $k;
  my $max_g;
  for ( 1 .. $n ) {
    my $g = g($_);
    if ( $g > $max_g ) {
      $k = $_;
      $max_g = $g;
    }
  }
  $k;
}
うむぅ、エレガントでない..
では、Language::Functionalモジュールを使ってみて、

#!perl
#

use strict;

use Language::Functional qw(:all);
use Time::HiRes;

my $t = Time::HiRes::time;
print h(100), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub f {
  my $n = shift;
  if ( $n == 1 ) {
    1;
  }
  elsif ( $n % 2 ) {
    $n*3+1;
  }
  else {
    $n/2;
  }
}

sub g {
  my $n = shift;
  my $c;
  Until { ++$c && shift() == 1; } \&f, $n;
  $c;
}

sub h {
  my $n = shift;
  my $max = maximum([map {g($_)} (1..$n)]);
  
  head(filter sub {g(shift) ==  $max}, [1..$n]);
}
....変わらねー T_T .
.
[追記]
よく考えたら f()は

sub f{
  my $n = shift;
  ($n % 2) ? $n*3+1 : $n/2;
}
で十分ですな。

[さらに追記]
もっと短くなった。わぁい(っても速度は変わらない(h(100000)で17.5秒くらい)けど)

#!perl
#

use strict;

sub g;
sub h;

use Time::HiRes;

my $t = Time::HiRes::time;
print h(100000), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub g {
  my $n = shift;
  $n == 1 ? 1 : 1 + g(($n%2) ? $n*3+1 : $n/2)
}

sub h {
  scalar((
    sort { $b->[1] <=> $a->[1] } 
    map { [$_, g($_)] } 1 .. shift
  )[0])->[0];
}
無駄にC++の機能を使ってCDドライブ排出プログラムを書いてみた。
元々はDeviceIoControl APIの使い方を調べてたんだけど.. まぁいいか

#include <windows.h>
#include <winioctl.h>

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <string>

class CdromDriveEnumerator : public std::iterator<std::input_iterator_tag, const std::string>
{
  DWORD dwDrives_;
  int index_;
  std::string drive_;

  public:
  CdromDriveEnumerator()
    : dwDrives_(GetLogicalDrives() << 1), index_(-1), drive_()
    {++(*this);}

  CdromDriveEnumerator(const CdromDriveEnumerator& x)
    : dwDrives_(x.dwDrives_), index_(x.index_), drive_(x.drive_)
    {}

  CdromDriveEnumerator& operator =(const CdromDriveEnumerator& x)
  {
    dwDrives_ = x.dwDrives_;
    index_ = x.index_;
    drive_ = x.drive_;
    return *this;
  }

  reference operator *() const
  {
    return drive_;
  }

  pointer operator ->() const
  {
    return &drive_;
  }

  CdromDriveEnumerator& operator ++()
  {
    ++index_;
    dwDrives_ >>= 1;
    if ( dwDrives_ & 1 ) {
      drive_ = std::string(1, static_cast<char>('A'+index_)).append(":");
      if ( GetDriveType(drive_.c_str()) != DRIVE_CDROM ) {
        ++(*this);
      }
    }
    else {
      ++(*this);
    }
    return *this;
  }

  CdromDriveEnumerator operator ++(int)
  {
    CdromDriveEnumerator ret = *this;
    ++(*this);
    return ret;
  }

  private:
  CdromDriveEnumerator(char drive)
    : dwDrives_(0), index_(0), drive_(std::string(1, drive).append(":"))
    {}

  public:
  static const CdromDriveEnumerator& end() {
    static CdromDriveEnumerator end('Z'+1);
    return end;
  }
};
bool operator ==(const CdromDriveEnumerator& x, const CdromDriveEnumerator& y)
{
  return *x == *y;
}
bool operator !=(const CdromDriveEnumerator& x, const CdromDriveEnumerator& y)
{
  return !(x == y);
} 

struct DriveEjector : public std::unary_function<const std::string&, int>
{
  result_type operator()(argument_type drive) {
    std::cout << "try to eject " << drive << std::endl;

    HANDLE h = CreateFile(
        std::string("\\\\.\\").append(drive).c_str(),
        GENERIC_READ,
        FILE_SHARE_READ,
        0,
        OPEN_EXISTING,
        0,
        0);

    if ( h == INVALID_HANDLE_VALUE ) {
      std::cerr << "failed to open volume \\\\.\\" << drive << std::endl;
      return 1;
    }

    DWORD dwReturned;
    for ( int i = 0; i < 20; ++i ) {
      if ( DeviceIoControl(h, FSCTL_LOCK_VOLUME, 0, 0, 0, 0, &dwReturned, 0) ) {
        if ( DeviceIoControl(h, FSCTL_DISMOUNT_VOLUME, 0, 0, 0, 0, &dwReturned, 0) ) {
          PREVENT_MEDIA_REMOVAL pmr;
          pmr.PreventMediaRemoval = FALSE;
          if ( DeviceIoControl(h, IOCTL_STORAGE_MEDIA_REMOVAL, 
                &pmr, sizeof(PREVENT_MEDIA_REMOVAL), 0, 0, &dwReturned, 0) ) {
            if ( DeviceIoControl(h, IOCTL_STORAGE_EJECT_MEDIA, 0, 0, 0, 0, &dwReturned, 0) ) {
              std::cout << "EJECT!" << std::endl;
            }
            break;
          }
        }
      }
    }

    CloseHandle(h);
    return 0;
  }
};

int main()
{
  std::for_each(CdromDriveEnumerator(), CdromDriveEnumerator::end(), DriveEjector());
  return 0;
}

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        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

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic