Varannan-problem

2014-12-04, 22:53 #1

Medlem

Reg: Mar 2010

Inlägg: 434

Jag har ett litet problem som jag funderar på. Egentligen är det ett mer abstrakt problem än vad som kommer visas här, men detta är en del i problemet och jag gör det till ett "vardagsexempel" för att det förhoppningsvis ska bli lättare att greppa problemet.

Jag vill placera ut facklor längst ett staket. Det ska finnas en fackla på första och sista staket och lika många jämt fördelade där emellan.

Om det är tex 10 st staketstycken kan man inte ta varannan eftersom den sista staketbiten då blir utan fakla:

Kod:

| | | | |
##########

.

Däremot fungerar det med 2 stycken staketbitar mellan varje fackla:

Kod:

|  |  |  |
##########

.

Om vi nu säger att jag har n stycken staketbitar. Hur löser jag det då?

__________________
Senast redigerad av fyma 2014-12-04 kl. 23:05.

Citera

2014-12-05, 00:31 #2

Medlem

Reg: Jun 2009

Inlägg: 535

Problemet är faktiskt inte så enkelt som man först tänker sig, och problematiken uppstår när det är ett jämnt antal hashtags man vill ha, som du själv verkar ha märkt. För jämna n gäller, att om du vill ha n hashtags, behöver du hitta divisorn till n-1. Ett exempel du själv nämner är n=10. Då är n-1 = 9, vilket är delbart med tre. Här kan vi faktorera till 3 och 3, vilket gör att intervallet på 10 hashtags kan delas upp jämnt på tre intervall med tre tecken i varje (ett | och två mellanslag), följt av ett avslutande |, precis som du själv noterat. Hur generaliserar man då detta? Skrev ihop lite kod en snabbis i matlab...

Kod:

function f = print_fence(n)


if mod(n,2) == 0

counter = 2;


% letar reda på minsta divisorn.
while mod((n-1),counter) ~= 0
counter = counter+1;
    
end



AmountOfRuns = (n-1)/counter
    
for i=1:AmountOfRuns

fprintf('|');
for i=1:(Divisor-1)
    fprintf(' ');
end

    
end

fprintf('|');
end

if mod(n,2)~= 0
for i=1:((n+1)/2)
fprintf('| ');
end
end
    

fprintf('\n');


for i=1:n
fprintf('#');
end
fprintf('\n');

...som gör precis det som du gjorde med n = 10. Detta resulterar i följande output för vissa n:

Kod:

>> print_fence(9)
| | | | | 
#########
>> print_fence(10)
|  |  |  |
##########

>> print_fence(50)
|      |      |      |      |      |      |      |
##################################################
>> print_fence(52)
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
####################################################
>> print_fence(94)
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
##############################################################################################

Input är alltså antalet hashtags.

Skulle man till exempel mata in 102, skulle det alltså bara bli två pinnar, efterom 101 är prim och intervallet går således inte att dela upp.
Kanske inte det utseende man skulle vilja ha på varje, men om man vill dela upp intervallet jämnt skulle jag inte kunna se hur det går att göra (eftersom att ett primtal inte går att dividera jämnt med något lägre heltal förutom 1). 50, däremot, ger n-1= 49, som ju kan delas upp i 7*7. Därmed får vi ett "snyggt" staket. Samma gäller för 94, som ger n-1=93.

__________________
Senast redigerad av KingRat 2014-12-05 kl. 00:33.

Citera

2014-12-05, 01:42 #3

Medlem

Reg: Mar 2010

Inlägg: 434

Wow! tack så jättemycket!

Garanterat användbart inom flera områden. Inte minst inom arkitekturen.

Går det lösa ytterliggare så output istället blir en array innehållande alla lösningar? Såhär ungefär:

Kod:

>> print_fence_arr(9)
|       |
#########

|   |   |
#########

| | | | |
#########

|||||||||
#########

Eller varför inte göra det till mängder?

Låt f(n) vara en mängd som representerar antalet möjliga facklor:

Kod:

f(2) = {2}
f(3) = {2, 3}
f(4) = {2, 4}
f(5) = {2, 3, 5}
f(6) = {2, 6}
f(7) = {2, 3, 4, 7}
f(8) = {2, 8}
f(9) = {2, 3, 5, 9}

Låt g(n) vara den mängd som representerar hur många stakets mellanrum det är mellan varje fackla:

Kod:

g(2) = {0}
g(3) = {0, 1}
g(4) = {0, 2}
g(5) = {0, 1, 3}
g(6) = {0, 4}
g(7) = {0, 1, 2, 5}
g(8) = {0, 6}
g(9) = {0, 1, 3, 7}

Men hur ser funktionerna ut egentligen?

__________________
Senast redigerad av fyma 2014-12-05 kl. 01:46.

Citera

2014-12-05, 21:07 #4

Medlem

Reg: Nov 2004

Inlägg: 88

Detta är (nästan) vanlig delbarhet:
S = Antal staketbitar
F = Antal facklor

Då gäller att lösningarna är alla F och S som uppfyller
F-1|S-1

'|' utläses 'delar'.

Med dina beteckningar:
f(n) = {x : x-1|n-1}

Finns ingen sluten form (googla integer factorization).

Citera

Varannan-problem

Stöd Flashback