Tävlingsprogrammering/Uppgifter/Ekvationer

Ekvationer

Ekvationer är viktiga inom matematiken och redan på högstadiet får man lära sig att lösa enklare typer. I den här uppgiften så ska du göra detsamma, men nu med hjälp av datorn.

Du ska skriva ett program som läser in en ekvation och löser den. Ekvationerna består av högst 20 tecken och innehåller för enkelhets skull endast ensiffriga tal (0–9), tecknen +, −, = och tecknet x, som är den okända variabeln. Det garanteras att varje ekvation innehåller precis ett likhetstecken, och att ekvationerna i övrigt är syntaktiskt korrekta. Närmare bestämt består de av ett antal termer (siffra eller x eller siffra x) och termerna åtskiljs av exakt ett av tecknen +,- eller =.

Programmet ska skriva ut det värde på x som löser ekvationen (minst sex decimaler vid behov). Om det inte finns något sådant värde, skriv istället ut “Ingen lösning”. Om det tvärtom finns oändligt många värden som löser ekvationen, skriv ut “Flera lösningar”.

Delpoäng kommer ges om programmet klarar alla fall med en unik lösning, eller om programmet klarar alla övriga fall.

Sex körningsexempel

Ekvation ? 3x+2=8-x
x = 1.5

Ekvation ? 0=8+3x
x = -2.666667

Ekvation ? x+7-9x=2+5x-3
x = 0.615385

Ekvation ? 3x+5=5-4x
x = 0

Ekvation ? 6x=6x
Flera lösningar

Ekvation ? x+1=x-1
Ingen lösning

Lösning

Låt programmet först addera och subtrahera på båda sidorna om likhetstecknet tills ekvationen står i någon enkel form som du själv bestämmer, exempelvis

ax + b = 0

Därefter är det ren matematik:

• Om a ≠ 0 dividerar vi med a och får x=-b/a
• Om a=b=0 så står det 0=0, vilket innebär att varje x är en lösning, d.v.s. det finns flera lösningar.
• Om a=0 men b ≠ 0 så står det t.ex. 1=0, vilket naturligtvis inte har någon lösning.

Även om du kanske inte sett dessa regler tidigare bör det inte vara särskilt svårt att klura ut dem.

Själva parsningen av strängen och reduceringen kan göras på många olika sätt. Här är ett exempel som visar att man inte behöver strängfunktioner alls, men det blir förstås ännu enklare med funktioner som Python's split().

Lösning i C:

#include <stdio.h>

int main() {
  char s[101];
  int i,a,b,st,sign,side,nop,coef,op[100];
  scanf("%s", s);
  nop=0;
  for(i=0;s[i];i++) if(s[i]=='+' || s[i]=='-' || s[i]=='=') 
     op[nop++]=i;  //Spara operatorernas placering i strängen
  op[nop++]=i;   //Lägg till en extra operator på slutet för bekvämlighets skull

  //Reducera ekvationen till ax + b = 0
  a=b=0;  
  st=0;     //index för att gå igenom strängen, börjar från början
  sign=1; //håller reda på vad senaste tecknet (plus/minus) var. Minus förekommer inte i början
  side=1; //håller reda på om vi har passerat likhetstecknet, i så fall subtraherar vi för att flytta över till vänsterledet
  for(i=0;i<nop;i++) {      //Loopa över varje term, d.v.s. läs fram till nästa operator
    if(s[st]>='0' && s[st]<='9') {    
      coef=s[st]-'0';    //Om första tecknet i termen är 0-9 så sparas detta tal...
      st++;
    }
    else coef=1;    //...annars förutsätts 1 
    coef*=side*sign;    //   Ta hänsyn till ev. minustecken och om termen står i högerledet
    if(s[st]=='x') a+=coef;      // Om termen innehåller x så läggs den till a 
    else if (st==op[i]) b+=coef;        //  ... och annars till b 
    else printf("Syntax error!\n");    //Detta inträffar förstås aldrig
    //Kolla nu på operatorn eftersom det påverkar de följande termerna. 
    if(s[op[i]]=='=') { side=-1; sign=1; }     //Första termen efter likhetstecknet är alltid positiv.
    else if(s[op[i]]=='-') sign=-1;
    else sign=1;
    st=op[i]+1;    //Fortsätt läsa tecknet närmast efter operatorn
  }

  if(a==0 && b==0) printf("Många lösningar\n");
  else if(a==0) printf("Ingen lösning\n");
  else printf("x = %f\n", -(double)b/(double)a);
  return 0;
}

En lösning skriven i Haskell där all magi sker med hjälp av pattern matching (av Anton Fors Hurdén):

solve a b _ ('=':t)             = solve a b (-1) t
solve a b s ('+':'x':t)         = solve (a + s) b s t
solve a b s ('-':'x':t)         = solve (a - s) b s t
solve a b s ('x':t)             = solve (a + s) b s t
solve a b s ('+':n:'x':t)       = solve (a + s * read [n]) b s t
solve a b s ('-':n:'x':t)       = solve (a - s * read [n]) b s t
solve a b s (n:'x':t)           = solve (a + s * read [n]) b s t
solve a b s ('+':n:t)           = solve a (b + s * read [n]) s t
solve a b s ('-':n:t)           = solve a (b - s * read [n]) s t
solve a b s (n:t)               = solve a (b + s * read [n]) s t
solve a b _ []  | a == b        = putStrLn "Flera lösningar"
                | a == 0        = putStrLn "Ingen lösning"
                | otherwise     = print $ fromIntegral (-b) / fromIntegral a

main = getLine >>= solve 0 0 1