Acm-valogato April 2012

acm-valogato@cs.bme.hu

1 participants
1 discussions

FoxAndPhotography -- miért elég csak az első sort cserélgetni

by Engedy, Balazs

Sziasztok! Eszembe jutott, hogyan lehet nagyon egyszerűen belátni, hogy csak az első sort elég manipulálni. Jelölje ehhez A az első és B a hátsó sort, és egy S cseresorozatot, ami (i,j) párokból áll (ahol |j-i|=1, és az indexek mindig az adott lépésben aktuális tömbre vonatkoznak). Ha B-re kellene egy S cseresorozatot alkalmazni, az ugyanaz, mintha S-et fordított sorrendben (ez legyen S') alkalmaznánk A-ra. Alkalmazzuk ugyanis S-et B-re, majd S'-t A és B-re együttesen (az egymáshoz tartozó első-hátsó párokat "összeragasztjuk"). Világos, hogy S' az S inverze is egyben, így B az eredeti sorrendre áll vissza, és az A és B-beli egymáshoz képesti viszonya rögtön az S alkalmazása után a megfelelő, az S' alkalmazása során pedig nem változott. Üdv, Balázs

12 years, 2 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

Acm-valogato April 2012