• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

djthyrax

[PHP]Sextas-feira 13

23 mensagens neste tópico

Boas. Andava eu pelo USACO quando me deparei com este problema:

Is Friday the 13th really an unusual event?

That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday over a given period of N years. The time period to test will be from January 1, 1900 to December 31, 1900+N-1 for a given number of years, N. N is non-negative and will not exceed 400.

There are few facts you need to know before you can solve this problem:

    * January 1, 1900 was on a Monday.

    * Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29.

    * Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year)

    * The rule above does not hold for century years. Century years divisible by 400 are leap years, all other are not. Thus, the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year.

Do not use any built-in date functions in your computer language.

Don't just precompute the answers, either, please.

PROGRAM NAME: friday

INPUT FORMAT

One line with the integer N.

SAMPLE INPUT (file friday.in)

20

OUTPUT FORMAT

Seven space separated integers on one line. These integers represent the number of times the 13th falls on Saturday, Sunday, Monday, Tuesday, ..., Friday.

SAMPLE OUTPUT (file friday.out)

36 33 34 33 35 35 34

E lembrei-me de criar qq coisa para descobrir as sextas-feira 13 num intervalo de anos :P

<?php
header("Content-Type: text/plain");
function microtime_float(){
   list($usec, $sec) = explode(" ", microtime());
   return ((float)$usec + (float)$sec);
}

$time_start = microtime_float();

set_time_limit(0);

// começa aqui

$n = 400; // anos a procurar

$sextas = 0;

$diasemana = 1; // monday
/*
1 - monday
2 - tuesday
3 - wednesday
4 - thursday
5 - friday
6 - saturday
7 - sunday
*/

for($i=1900;$i<1900+$n;$i++){
if($i%4 == 0){ # ano bissexto
	$fev = 29;
}else $fev = 28;

for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." January ".$i."\n";
	}
}

for($ii=1;$ii<=$fev;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." February ".$i."\n";
	}
}

for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." March ".$i."\n";
	}
}
for($ii=1;$ii<=30;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." April ".$i."\n";
	}
}
for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." May ".$i."\n";
	}
}
for($ii=1;$ii<=30;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." June ".$i."\n";
	}
}

for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." July ".$i."\n";
	}
}

for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." August ".$i."\n";
	}
}

for($ii=1;$ii<=30;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." September ".$i."\n";
	}
}
for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." October ".$i."\n";
	}
}

for($ii=1;$ii<=30;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." November ".$i."\n";
	}
}
for($ii=1;$ii<=31;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo $ii." December ".$i."\n";
	}
}
}
echo "\n\n\n$sextas Fridays";

// fim
$time_end = microtime_float();
$time = $time_end - $time_start;

echo "\n\n\n\n$time seconds\n";	
?>

Timings:

500000 - 332.40723896 seconds

50000  - 19.3930888176 seconds

5000  - 1.89415287971 seconds

500    - 0.183122873306 seconds

50    - 0.0123970508575 seconds

5      - 0.00130200386047 seconds

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, nem olhei muito para o código, mas.. aqueles for's todos não me parecem necessários...

A propósito, já resolveste esse problema do USACO? Usaste isso tudo também? tsc tsc tsc...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, nem olhei muito para o código, mas.. aqueles for's todos não me parecem necessários...

A propósito, já resolveste esse problema do USACO? Usaste isso tudo também? tsc tsc tsc...

Eu usei aqueles for's porque não me dei ao trabalho de declarar uma função para isso xD E não, ainda não resolvi no USACO, estou chateado com o C. :P
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Lol para entrar na brincadeira aqui vai outra maneira (apesar de mais lenta) mas com menus código :P

<?php
set_time_limit(0);
function date_new($var,$option = NULL)
{	
list($month,$day,$year) = explode("/",jdtogregorian($var));
if ($option == "day")
	return $day;
elseif ($option == "month")
	return $month;
elseif ($option == "year")
	return $year;
else
	return $year."/".$month."/".$year;
}

//Número de anos a considerar:
$years = 5000;

$today = cal_to_jd(CAL_GREGORIAN, date("m"), date("d"), date("Y"));

while (jddayofweek($today) != 5)
$today += 1;

$last_year = date_new($today,"year");
$final_year = $last_year+$years;
$count++;
while ($last_year<=$final_year)
{
if (date_new($today,"year") != $last_year)
	$last_year++;
if (date_new($today,"day") == 13) 
	$count++;

$today += 7;
}
echo $count." Friday the 13th until ".$final_year;
?>

Nem confirmei se isto está 100% correcto alguém que compare e verifique se sim :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Encurtei o código:

<?php
header("Content-Type: text/plain");
function microtime_float(){
   list($usec, $sec) = explode(' ', microtime());
   return ((float)$usec + (float)$sec);
}

set_time_limit(0);

$time_start = microtime_float();

// começa aqui

function sextas($limit, $m){
global $diasemana, $i, $sextas;
for($ii=1;$ii<=$limit;$ii++){
	if($diasemana == 7){
		$diasemana = 1;
	}else $diasemana++;
	if($ii == 13 && $diasemana == 5){
		$sextas++;
		echo "$ii $m $i\n";
	}
}
}

$n = 5; // anos a procurar

$sextas = 0;

$diasemana = 1; // monday
/*
1 - monday
2 - tuesday
3 - wednesday
4 - thursday
5 - friday
6 - saturday
7 - sunday
*/

for($i=1900;$i<1900+$n;$i++){
if($i%4 == 0){ # ano bissexto
	$fev = 29;
}else $fev = 28;

sextas(31, 'January');
sextas($fev, 'February');
sextas(31, 'March');
sextas(30, 'April');
sextas(31, 'May');
sextas(30, 'June');
sextas(31, 'July');
sextas(31, 'August');
sextas(30, 'September');
sextas(31, 'October');
sextas(30, 'November');
sextas(31, 'December');
}
echo "\n\n\n$sextas Fridays";

// fim
$time_end = microtime_float();
$time = $time_end - $time_start;

echo "\n\n\n\n$time seconds\n";	
?>

Timings:

500000 - 320.727806807 seconds

50000  - 19.3638679981 seconds

5000  - 1.78756189346 seconds

500    - 0.172668933868 seconds

50    - 0.0132169723511 seconds

5      - 0.00127220153809 seconds

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

@djthyrax

Modifiquei o teu código espero que não leves a mal :P

<?php
set_time_limit(0);

fridays( 20 );  //20 anos

function fridays( $years ){

        $fridays = 0;
        $dayofweak = 1;
        $startYear= 1900;

        $months = array( 'January' => 31, 'February' => ($startYear%4 == 0) ? 29 : 28, 'March' => 30, 'April' => 31, 'May' => 30, 'June' => 31, 'July' => 30, 'August' => 31, 'September' => 30, 'October' => 31, 'November' => 30, 'December' => 31 );

        while($startYear < 1900+$years) {

                foreach( $months as $month => $day ) {

                        for($i = 1;$i <= $day;$i++ ){
                                $dayofweak = ($dayofweak == 7) ?  1 : $dayofweak+1;

                                if($i == 13 && $dayofweak == 5) {
                                        $fridays++;
                                        echo "$i $month $startYear\r\n";
                                }
                        }
                }
                $startYear++;
        }
        echo "\n\n$fridays Fridays\r\n";
}
?>

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porra, até já me ripam o código e o carai! :P

Já agora, mete aí os timings :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Timings:

50000 - 41.586336135864 seconds

5000 - 4.5795860290527 seconds

500 - 0.29068493843079 seconds

50 - 0.018600940704346 seconds

5 - 0.0019280910491943 seconds

PS: Podes ter acerteza que ainda vou ripar muitos códigos teus  :P :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Timings:

50000 - 41.586336135864 seconds

5000 - 4.5795860290527 seconds

500 - 0.29068493843079 seconds

50 - 0.018600940704346 seconds

5 - 0.0019280910491943 seconds

PS: Podes ter acerteza que ainda vou ripar muitos códigos teus  :P :P

Qual é o teu processador? ???

LOL, porque vais ripar muito código meu? :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Qual é o teu processador? ???

O processador do PC onde tenho o linux é um AMD Sempron 2800 1.6 ghz  x(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Qual é o teu processador? ???

O processador do PC onde tenho o linux é um AMD Sempron 2800 1.6 ghz  x(

Pois, também me pareceu, eu tenho um Athlon64 3000+ @ 1.8 GHz :P Já agora, qt tempo demora 500000?
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

...Já agora, qt tempo demora 500000?

500000 - 519.50875496864 seconds

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

...Já agora, qt tempo demora 500000?

500000 - 519.50875496864 seconds

Wow, é uma beca ... mais lento que o meu :|
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

...Já agora, qt tempo demora 500000?

500000 - 519.50875496864 seconds

Wow, é uma beca ... mais lento que o meu :|

vou experimentar o teu código no meu PC para ver quanto tempo demora "500000"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O teu código é uma beca mais rapido :P

500000 - 421.0588350296 seconds

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Alguém reparou que isso não está a dar as sextas feiras correctas?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Alguém reparou que isso não está a dar as sextas feiras correctas?

Eu regime pelo enunciado do USACO que está no 1º post. :)
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu também, e deu-me as correctas. Isto em C++. Até porque o enunciado está correcto, 01/01/1900 foi uma 2ª feira.

E já agora, só estão a testar se um ano é bissexto pela divisibilidade por 4, o que vai dar que 1900, 2100 e 2200 sejam bissextos quando não o foram. Isto basta para que dê as sextas erradas...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu também, e deu-me as correctas. Isto em C++. Até porque o enunciado está correcto, 01/01/1900 foi uma 2ª feira.

E já agora, só estão a testar se um ano é bissexto pela divisibilidade por 4, o que vai dar que 1900, 2100 e 2200 sejam bissextos quando não o foram. Isto basta para que dê as sextas erradas...

Err, então quando tiver tempo substituo o %4. 1900 foi bissexto certo?
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. As viragens de século bissextas foram 400, 800, 1200, 1600, 2000, e hão de ser 2400, 2800, etc se lá chegarmos. Quero dizer, nós não. Pelo menos nesta vida... ::)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. As viragens de século bissextas foram 400, 800, 1200, 1600, 2000, e hão de ser 2400, 2800, etc se lá chegarmos. Quero dizer, nós não. Pelo menos nesta vida... ::cheesygrin:

Tipo, se 2000 foi bissexto, este código deveria dar os anos bissextos:

$i=2000;
while($i >= 1900){
$i-=4;
echo $i."\n";
}

Mas tu dizes que 1900 não é bissexto quando o script diz que é.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mais um rip do código original do djthyrax, agora já dá as datas certas.

<?php
header("Content-Type: text/plain");

function microtime_float(){
   list($usec, $sec) = explode(' ', microtime());
   return ((float)$usec + (float)$sec);
}

set_time_limit(0);

$time_start = microtime_float();

// começa aqui

$n = 400; // anos a procurar

/*	Dias organizados conforme o output pedido:
1 - saturday
2 - sunday
3 - monday
4 - tuesday
5 - wednesday
6 - thursday
7 - friday
*/ 
$diasemana = 3; //1º Janeiro de 1900 era segunda-feira
$contagem = array( 1=>0,0,0,0,0,0,0); 

for($i=1900;$i<1900+$n;$i++){
if($i%100 == 0) { //Anos de século
	($i%400 == 0) ? $fev = 29 : $fev = 28;
}
else { //Anos normais
	($i%4 == 0) ? $fev = 29 : $fev = 28;
}
$meses = array(31, $fev, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);

foreach($meses as $key=>$limite) { //Passar por todos os meses
	for($ii=1; $ii<=$limite; $ii++) { //Passar por todos os dias do mês
		if($ii == 13) $contagem[$diasemana]++;
//			if($ii == 13 && $diasemana == 7) echo "Sexta-feira, $ii/".($key+1)."/$i)\n";
		$diasemana ++;
		if($diasemana == 8) $diasemana = 1;
	}
}
}

foreach($contagem as $value) echo "$value ";

// fim
$time_end = microtime_float();
$time = $time_end - $time_start;

echo "\n\n$time seconds\n";	


?>

Resultado:

684 687 685 685 687 684 688 

0.069061994552612 seconds

684 sábados, (...) e 688 sextas-feiras.  :biggrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora