cpp codes Archives - Pro Programming

Program to find Inverse of Matrix C++

Today we are going to write a program to find the inverse of matrix C++, so let’s start with the what is the inverse of a matrix.

Inverse of a Matrix:

For a square matrix A, the inverse is written A^-1. When A is multiplied by A^-1 the result is the identity matrix I. Non-square matrices do not have inverses.

Note: Not all square matrices have inverses. A square matrix which has an inverse is called invertible or nonsingular, and a square matrix without an inverse is called non-invertible or singular.

AA^-1 = A^-1A = I

Example:	For matrix , its inverse is since
	AA^-1 = and A^-1A = .

Program to find Inverse of a Matrix C++:



#if !defined(MATRIX_H)

#define MATRIX_H

#include &lt;stdio.h&gt;

#include &lt;iostream&gt;

#include &lt;tchar.h&gt;

#include &lt;math.h&gt;

#include &lt;stdlib.h&gt;

class CMatrix

{

    private:

        int m_rows;

        int m_cols;

        char m_name[128];

        CMatrix();

    public:

        double **m_pData;

        CMatrix(const char *name, int rows, int cols) :

            m_rows(rows), m_cols(cols)

        {

            strcpy(m_name, name);

            m_pData = new double*[m_rows];

            for (int i = 0; i &lt; m_rows; i++)

                m_pData[i] = new double[m_cols];

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    m_pData[i][j] = 0.0;

                }

            }

        }

        CMatrix(const CMatrix &amp;other)

        {

            strcpy(m_name, other.m_name);

            m_rows = other.m_rows;

            m_cols = other.m_cols;

            m_pData = new double*[m_rows];

            for (int i = 0; i &lt; m_rows; i++)

                m_pData[i] = new double[m_cols];

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    m_pData[i][j] = other.m_pData[i][j];

                }

            }

        }

        ~CMatrix()

        {

            for (int i = 0; i &lt; m_rows; i++)

                delete[] m_pData[i];

            delete[] m_pData;

            m_rows = m_cols = 0;

        }

        void SetName(const char *name)

        {

            strcpy(m_name, name);

        }

        const char* GetName() const

        {

            return m_name;

        }

        void GetInput()

        {

            std::cin &gt;&gt; *this;

        }

        void FillSimulatedInput()

        {

            static int factor1 = 1, factor2 = 2;

            std::cout &lt;&lt; "<strong>\n\n</strong>Enter Input For Matrix : " &lt;&lt; m_name &lt;&lt; " Rows: "

                    &lt;&lt; m_rows &lt;&lt; " Cols: " &lt;&lt; m_cols &lt;&lt; "<strong>\n</strong>";

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    std::cout &lt;&lt; "Input For Row: " &lt;&lt; i + 1 &lt;&lt; " Col: " &lt;&lt; j

                            + 1 &lt;&lt; " = ";

                    int data = ((i + 1) * factor1) + (j + 1) * factor2;

                    m_pData[i][j] = data / 10.2;

                    std::cout &lt;&lt; m_pData[i][j] &lt;&lt; "<strong>\n</strong>";

                    factor1 += (rand() % 4);

                    factor2 += (rand() % 3);

                }

                std::cout &lt;&lt; "<strong>\n</strong>";

            }

            std::cout &lt;&lt; "<strong>\n</strong>";

        }

        double Determinant()

        {

            double det = 0;

            double **pd = m_pData;

            switch (m_rows)

            {

                case 2:

                {

                    det = pd[0][0] * pd[1][1] - pd[0][1] * pd[1][0];

                    return det;

                }

                    break;

                case 3:

                {

                    <em>/***</em>

<em>                     a b c</em>

<em>                     d e f</em>

<em>                     g h i</em>




<em>                     a b c a b c</em>

<em>                     d e f d e f</em>

<em>                     g h i g h i</em>




<em>                     // det (A) = aei + bfg + cdh - afh - bdi - ceg.</em>

<em>                     ***/</em>

                    double a = pd[0][0];

                    double b = pd[0][1];

                    double c = pd[0][2];

                    double d = pd[1][0];

                    double e = pd[1][1];

                    double f = pd[1][2];

                    double g = pd[2][0];

                    double h = pd[2][1];

                    double i = pd[2][2];

                    double det = (a * e * i + b * f * g + c * d * h);

                    det = det - a * f * h;

                    det = det - b * d * i;

                    det = det - c * e * g;

                    return det;

                }

                    break;

                case 4:

                {

                    CMatrix *temp[4];

                    for (int i = 0; i &lt; 4; i++)

                        temp[i] = new CMatrix("", 3, 3);

                    for (int k = 0; k &lt; 4; k++)

                    {

                        for (int i = 1; i &lt; 4; i++)

                        {

                            int j1 = 0;

                            for (int j = 0; j &lt; 4; j++)

                            {

                                if (k == j)

                                    continue;

                                temp[k]-&gt;m_pData[i - 1][j1++]

                                        = this-&gt;m_pData[i][j];

                            }

                        }

                    }

                    double det = this-&gt;m_pData[0][0] * temp[0]-&gt;Determinant()

                            - this-&gt;m_pData[0][1] * temp[1]-&gt;Determinant()

                            + this-&gt;m_pData[0][2] * temp[2]-&gt;Determinant()

                            - this-&gt;m_pData[0][3] * temp[3]-&gt;Determinant();

                    return det;

                }

                    break;

                case 5:

                {

                    CMatrix *temp[5];

                    for (int i = 0; i &lt; 5; i++)

                        temp[i] = new CMatrix("", 4, 4);

                    for (int k = 0; k &lt; 5; k++)

                    {

                        for (int i = 1; i &lt; 5; i++)

                        {

                            int j1 = 0;

                            for (int j = 0; j &lt; 5; j++)

                            {

                                if (k == j)

                                    continue;

                                temp[k]-&gt;m_pData[i - 1][j1++]

                                        = this-&gt;m_pData[i][j];

                            }

                        }

                    }

                    double det = this-&gt;m_pData[0][0] * temp[0]-&gt;Determinant()

                            - this-&gt;m_pData[0][1] * temp[1]-&gt;Determinant()

                            + this-&gt;m_pData[0][2] * temp[2]-&gt;Determinant()

                            - this-&gt;m_pData[0][3] * temp[3]-&gt;Determinant()

                            + this-&gt;m_pData[0][4] * temp[4]-&gt;Determinant();

                    return det;

                }

                case 6:

                case 7:

                case 8:

                case 9:

                case 10:

                case 11:

                case 12:

                default:

                {

                    int DIM = m_rows;

                    CMatrix **temp = new CMatrix*[DIM];

                    for (int i = 0; i &lt; DIM; i++)

                        temp[i] = new CMatrix("", DIM - 1, DIM - 1);

                    for (int k = 0; k &lt; DIM; k++)

                    {

                        for (int i = 1; i &lt; DIM; i++)

                        {

                            int j1 = 0;

                            for (int j = 0; j &lt; DIM; j++)

                            {

                                if (k == j)

                                    continue;

                                temp[k]-&gt;m_pData[i - 1][j1++]

                                        = this-&gt;m_pData[i][j];

                            }

                        }

                    }

                    double det = 0;

                    for (int k = 0; k &lt; DIM; k++)

                    {

                        if ((k % 2) == 0)

                            det = det + (this-&gt;m_pData[0][k]

                                    * temp[k]-&gt;Determinant());

                        else

                            det = det - (this-&gt;m_pData[0][k]

                                    * temp[k]-&gt;Determinant());

                    }

                    for (int i = 0; i &lt; DIM; i++)

                        delete temp[i];

                    delete[] temp;

                    return det;

                }

                    break;

            }

        }

        CMatrix&amp; operator =(const CMatrix &amp;other)

        {

            if (this-&gt;m_rows != other.m_rows || this-&gt;m_cols != other.m_cols)

            {

                std::cout

                        &lt;&lt; "WARNING: Assignment is taking place with by changing the number of rows and columns of the matrix";

            }

            for (int i = 0; i &lt; m_rows; i++)

                delete[] m_pData[i];

            delete[] m_pData;

            m_rows = m_cols = 0;

            strcpy(m_name, other.m_name);

            m_rows = other.m_rows;

            m_cols = other.m_cols;

            m_pData = new double*[m_rows];

            for (int i = 0; i &lt; m_rows; i++)

                m_pData[i] = new double[m_cols];

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    m_pData[i][j] = other.m_pData[i][j];

                }

            }

            return *this;

        }

        CMatrix CoFactor()

        {

            CMatrix cofactor("COF", m_rows, m_cols);

            if (m_rows != m_cols)

                return cofactor;

            if (m_rows &lt; 2)

                return cofactor;

            else if (m_rows == 2)

            {

                cofactor.m_pData[0][0] = m_pData[1][1];

                cofactor.m_pData[0][1] = -m_pData[1][0];

                cofactor.m_pData[1][0] = -m_pData[0][1];

                cofactor.m_pData[1][1] = m_pData[0][0];

                return cofactor;

            }

            else if (m_rows &gt;= 3)

            {

                int DIM = m_rows;

                CMatrix ***temp = new CMatrix**[DIM];

                for (int i = 0; i &lt; DIM; i++)

                    temp[i] = new CMatrix*[DIM];

                for (int i = 0; i &lt; DIM; i++)

                    for (int j = 0; j &lt; DIM; j++)

                        temp[i][j] = new CMatrix("", DIM - 1, DIM - 1);

                for (int k1 = 0; k1 &lt; DIM; k1++)

                {

                    for (int k2 = 0; k2 &lt; DIM; k2++)

                    {

                        int i1 = 0;

                        for (int i = 0; i &lt; DIM; i++)

                        {

                            int j1 = 0;

                            for (int j = 0; j &lt; DIM; j++)

                            {

                                if (k1 == i || k2 == j)

                                    continue;

                                temp[k1][k2]-&gt;m_pData[i1][j1++]

                                        = this-&gt;m_pData[i][j];

                            }

                            if (k1 != i)

                                i1++;

                        }

                    }

                }

                bool flagPositive = true;

                for (int k1 = 0; k1 &lt; DIM; k1++)

                {

                    flagPositive = ((k1 % 2) == 0);

                    for (int k2 = 0; k2 &lt; DIM; k2++)

                    {

                        if (flagPositive == true)

                        {

                            cofactor.m_pData[k1][k2]

                                    = temp[k1][k2]-&gt;Determinant();

                            flagPositive = false;

                        }

                        else

                        {

                            cofactor.m_pData[k1][k2]

                                    = -temp[k1][k2]-&gt;Determinant();

                            flagPositive = true;

                        }

                    }

                }

                for (int i = 0; i &lt; DIM; i++)

                    for (int j = 0; j &lt; DIM; j++)

                        delete temp[i][j];

                for (int i = 0; i &lt; DIM; i++)

                    delete[] temp[i];

                delete[] temp;

            }

            return cofactor;

        }

        CMatrix Adjoint()

        {

            CMatrix cofactor("COF", m_rows, m_cols);

            CMatrix adj("ADJ", m_rows, m_cols);

            if (m_rows != m_cols)

                return adj;

            cofactor = this-&gt;CoFactor();

            // adjoint is transpose of a cofactor of a matrix

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    adj.m_pData[j][i] = cofactor.m_pData[i][j];

                }

            }

            return adj;

        }

        CMatrix Transpose()

        {

            CMatrix trans("TR", m_cols, m_rows);

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    trans.m_pData[j][i] = m_pData[i][j];

                }

            }

            return trans;

        }

        CMatrix Inverse()

        {

            CMatrix cofactor("COF", m_rows, m_cols);

            CMatrix inv("INV", m_rows, m_cols);

            if (m_rows != m_cols)

                return inv;

            // to find out Determinant

            double det = Determinant();

            cofactor = this-&gt;CoFactor();

            // inv = transpose of cofactor / Determinant

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    inv.m_pData[j][i] = cofactor.m_pData[i][j] / det;

                }

            }

            return inv;

        }

        CMatrix operator +(const CMatrix &amp;other)

        {

            if (this-&gt;m_rows != other.m_rows || this-&gt;m_cols != other.m_cols)

            {

                std::cout

                        &lt;&lt; "Addition could not take place because number of rows and columns are different between the two matrices";

                return *this;

            }

            CMatrix result("", m_rows, m_cols);

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    result.m_pData[i][j] = this-&gt;m_pData[i][j]

                            + other.m_pData[i][j];

                }

            }

            return result;

        }

        CMatrix operator -(const CMatrix &amp;other)

        {

            if (this-&gt;m_rows != other.m_rows || this-&gt;m_cols != other.m_cols)

            {

                std::cout

                        &lt;&lt; "Subtraction could not take place because number of rows and columns are different between the two matrices";

                return *this;

            }

            CMatrix result("", m_rows, m_cols);

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    result.m_pData[i][j] = this-&gt;m_pData[i][j]

                            - other.m_pData[i][j];

                }

            }

            return result;

        }

        CMatrix operator *(const CMatrix &amp;other)

        {

            if (this-&gt;m_cols != other.m_rows)

            {

                std::cout

                        &lt;&lt; "Multiplication could not take place because number of columns of 1st Matrix and number of rows in 2nd Matrix are different";

                return *this;

            }

            CMatrix result("", this-&gt;m_rows, other.m_cols);

            for (int i = 0; i &lt; this-&gt;m_rows; i++)

            {

                for (int j = 0; j &lt; other.m_cols; j++)

                {

                    for (int k = 0; k &lt; this-&gt;m_cols; k++)

                    {

                        result.m_pData[i][j] += this-&gt;m_pData[i][k]

                                * other.m_pData[k][j];

                    }

                }

            }

            return result;

        }

        bool operator ==(const CMatrix &amp;other)

        {

            if (this-&gt;m_rows != other.m_rows || this-&gt;m_cols != other.m_cols)

            {

                std::cout

                        &lt;&lt; "Comparision could not take place because number of rows and columns are different between the two matrices";

                return false;

            }

            CMatrix result("", m_rows, m_cols);

            bool bEqual = true;

            for (int i = 0; i &lt; m_rows; i++)

            {

                for (int j = 0; j &lt; m_cols; j++)

                {

                    if (this-&gt;m_pData[i][j] != other.m_pData[i][j])

                        bEqual = false;

                }

            }

            return bEqual;

        }

        friend std::istream&amp; operator &gt;&gt;(std::istream &amp;is, CMatrix &amp;m);

        friend std::ostream&amp; operator &lt;&lt;(std::ostream &amp;os, const CMatrix &amp;m);

};

std::istream&amp; operator &gt;&gt;(std::istream &amp;is, CMatrix &amp;m)

{

    std::cout &lt;&lt; "<strong>\n\n</strong>Enter Input For Matrix : " &lt;&lt; m.m_name &lt;&lt; " Rows: "

            &lt;&lt; m.m_rows &lt;&lt; " Cols: " &lt;&lt; m.m_cols &lt;&lt; "<strong>\n</strong>";

    for (int i = 0; i &lt; m.m_rows; i++)

    {

        for (int j = 0; j &lt; m.m_cols; j++)

        {

            std::cout &lt;&lt; "Input For Row: " &lt;&lt; i + 1 &lt;&lt; " Col: " &lt;&lt; j + 1

                    &lt;&lt; " = ";

            is &gt;&gt; m.m_pData[i][j];

        }

        std::cout &lt;&lt; "<strong>\n</strong>";

    }

    std::cout &lt;&lt; "<strong>\n</strong>";

    return is;

}

std::ostream&amp; operator &lt;&lt;(std::ostream &amp;os, const CMatrix &amp;m)

{




    os &lt;&lt; "<strong>\n\n</strong>Matrix : " &lt;&lt; m.m_name &lt;&lt; " Rows: " &lt;&lt; m.m_rows &lt;&lt; " Cols: "

            &lt;&lt; m.m_cols &lt;&lt; "<strong>\n\n</strong>";

    for (int i = 0; i &lt; m.m_rows; i++)

    {

        os &lt;&lt; " | ";

        for (int j = 0; j &lt; m.m_cols; j++)

        {

            char buf[32];

            double data = m.m_pData[i][j];

            if (m.m_pData[i][j] &gt; -0.00001 &amp;&amp; m.m_pData[i][j] &lt; 0.00001)

                data = 0;

            sprintf(buf, "%10.2lf ", data);

            os &lt;&lt; buf;

        }

        os &lt;&lt; "|<strong>\n</strong>";

    }

    os &lt;&lt; "<strong>\n\n</strong>";

    return os;

}

#endif

int main()

{

    CMatrix a("A", 5, 5);

    //std::cin &gt;&gt; a;

    a.FillSimulatedInput();

    CMatrix aadj = a.Inverse();

    std::cout &lt;&lt; a;

    std::cout &lt;&lt; aadj;

    CMatrix unit = (a * aadj);

    unit.SetName("A * A-Inv");

    std::cout &lt;&lt; unit;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

1001

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1012

1013

1014

1015

1016

1017

1018

1019

1020

#if !defined(MATRIX_H)

#define MATRIX_H

#include <stdio.h>

#include <iostream>

#include <tchar.h>

#include <math.h>

#include <stdlib.h>

class CMatrix

{

private:

int m_rows;

int m_cols;

char m_name[128];

CMatrix();

public:

double **m_pData;

CMatrix(const char *name, int rows, int cols) :

m_rows(rows), m_cols(cols)

{

strcpy(m_name, name);

m_pData = new double*[m_rows];

for (int i = 0; i < m_rows; i++)

m_pData[i] = new double[m_cols];

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

m_pData[i][j] = 0.0;

}

CMatrix(const CMatrix &other)

{

strcpy(m_name, other.m_name);

m_rows = other.m_rows;

m_cols = other.m_cols;

m_pData = new double*[m_rows];

for (int i = 0; i < m_rows; i++)

m_pData[i] = new double[m_cols];

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

m_pData[i][j] = other.m_pData[i][j];

}

~CMatrix()

{

for (int i = 0; i < m_rows; i++)

delete[] m_pData[i];

delete[] m_pData;

m_rows = m_cols = 0;

}

void SetName(const char *name)

{

strcpy(m_name, name);

}

const char* GetName() const

{

return m_name;

}

void GetInput()

{

std::cin >> *this;

}

void FillSimulatedInput()

{

static int factor1 = 1, factor2 = 2;

std::cout << "\n\nEnter Input For Matrix : " << m_name << " Rows: "

<< m_rows << " Cols: " << m_cols << "\n";

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

std::cout << "Input For Row: " << i + 1 << " Col: " << j

+ 1 << " = ";

int data = ((i + 1) * factor1) + (j + 1) * factor2;

m_pData[i][j] = data / 10.2;

std::cout << m_pData[i][j] << "\n";

factor1 += (rand() % 4);

factor2 += (rand() % 3);

}

std::cout << "\n";

}

std::cout << "\n";

}

double Determinant()

{

double det = 0;

double **pd = m_pData;

switch (m_rows)

{

case 2:

{

det = pd[0][0] * pd[1][1] - pd[0][1] * pd[1][0];

return det;

}

break;

case 3:

{

/***

a b c

d e f

g h i

a b c a b c

d e f d e f

g h i g h i

// det (A) = aei + bfg + cdh - afh - bdi - ceg.

***/

double a = pd[0][0];

double b = pd[0][1];

double c = pd[0][2];

double d = pd[1][0];

double e = pd[1][1];

double f = pd[1][2];

double g = pd[2][0];

double h = pd[2][1];

double i = pd[2][2];

double det = (a * e * i + b * f * g + c * d * h);

det = det - a * f * h;

det = det - b * d * i;

det = det - c * e * g;

return det;

}

break;

case 4:

{

CMatrix *temp[4];

for (int i = 0; i < 4; i++)

temp[i] = new CMatrix("", 3, 3);

for (int k = 0; k < 4; k++)

{

for (int i = 1; i < 4; i++)

{

int j1 = 0;

for (int j = 0; j < 4; j++)

{

if (k == j)

continue;

temp[k]->m_pData[i - 1][j1++]

= this->m_pData[i][j];

}

double det = this->m_pData[0][0] * temp[0]->Determinant()

- this->m_pData[0][1] * temp[1]->Determinant()

+ this->m_pData[0][2] * temp[2]->Determinant()

- this->m_pData[0][3] * temp[3]->Determinant();

return det;

}

break;

case 5:

{

CMatrix *temp[5];

for (int i = 0; i < 5; i++)

temp[i] = new CMatrix("", 4, 4);

for (int k = 0; k < 5; k++)

{

for (int i = 1; i < 5; i++)

{

int j1 = 0;

for (int j = 0; j < 5; j++)

{

if (k == j)

continue;

temp[k]->m_pData[i - 1][j1++]

= this->m_pData[i][j];

}

double det = this->m_pData[0][0] * temp[0]->Determinant()

- this->m_pData[0][1] * temp[1]->Determinant()

+ this->m_pData[0][2] * temp[2]->Determinant()

- this->m_pData[0][3] * temp[3]->Determinant()

+ this->m_pData[0][4] * temp[4]->Determinant();

return det;

}

case 6:

case 7:

case 8:

case 9:

case 10:

case 11:

case 12:

default:

{

int DIM = m_rows;

CMatrix **temp = new CMatrix*[DIM];

for (int i = 0; i < DIM; i++)

temp[i] = new CMatrix("", DIM - 1, DIM - 1);

for (int k = 0; k < DIM; k++)

{

for (int i = 1; i < DIM; i++)

{

int j1 = 0;

for (int j = 0; j < DIM; j++)

{

if (k == j)

continue;

temp[k]->m_pData[i - 1][j1++]

= this->m_pData[i][j];

}

double det = 0;

for (int k = 0; k < DIM; k++)

{

if ((k % 2) == 0)

det = det + (this->m_pData[0][k]

* temp[k]->Determinant());

else

det = det - (this->m_pData[0][k]

* temp[k]->Determinant());

}

for (int i = 0; i < DIM; i++)

delete temp[i];

delete[] temp;

return det;

}

break;

}

CMatrix& operator =(const CMatrix &other)

{

if (this->m_rows != other.m_rows || this->m_cols != other.m_cols)

{

std::cout

<< "WARNING: Assignment is taking place with by changing the number of rows and columns of the matrix";

}

for (int i = 0; i < m_rows; i++)

delete[] m_pData[i];

delete[] m_pData;

m_rows = m_cols = 0;

strcpy(m_name, other.m_name);

m_rows = other.m_rows;

m_cols = other.m_cols;

m_pData = new double*[m_rows];

for (int i = 0; i < m_rows; i++)

m_pData[i] = new double[m_cols];

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

m_pData[i][j] = other.m_pData[i][j];

}

return *this;

}

CMatrix CoFactor()

{

CMatrix cofactor("COF", m_rows, m_cols);

if (m_rows != m_cols)

return cofactor;

if (m_rows < 2)

return cofactor;

else if (m_rows == 2)

{

cofactor.m_pData[0][0] = m_pData[1][1];

cofactor.m_pData[0][1] = -m_pData[1][0];

cofactor.m_pData[1][0] = -m_pData[0][1];

cofactor.m_pData[1][1] = m_pData[0][0];

return cofactor;

}

else if (m_rows >= 3)

{

int DIM = m_rows;

CMatrix ***temp = new CMatrix**[DIM];

for (int i = 0; i < DIM; i++)

temp[i] = new CMatrix*[DIM];

for (int i = 0; i < DIM; i++)

for (int j = 0; j < DIM; j++)

temp[i][j] = new CMatrix("", DIM - 1, DIM - 1);

for (int k1 = 0; k1 < DIM; k1++)

{

for (int k2 = 0; k2 < DIM; k2++)

{

int i1 = 0;

for (int i = 0; i < DIM; i++)

{

int j1 = 0;

for (int j = 0; j < DIM; j++)

{

if (k1 == i || k2 == j)

continue;

temp[k1][k2]->m_pData[i1][j1++]

= this->m_pData[i][j];

}

if (k1 != i)

i1++;

}

bool flagPositive = true;

for (int k1 = 0; k1 < DIM; k1++)

{

flagPositive = ((k1 % 2) == 0);

for (int k2 = 0; k2 < DIM; k2++)

{

if (flagPositive == true)

{

cofactor.m_pData[k1][k2]

= temp[k1][k2]->Determinant();

flagPositive = false;

}

else

{

cofactor.m_pData[k1][k2]

= -temp[k1][k2]->Determinant();

flagPositive = true;

}

for (int i = 0; i < DIM; i++)

for (int j = 0; j < DIM; j++)

delete temp[i][j];

for (int i = 0; i < DIM; i++)

delete[] temp[i];

delete[] temp;

}

return cofactor;

}

CMatrix Adjoint()

{

CMatrix cofactor("COF", m_rows, m_cols);

CMatrix adj("ADJ", m_rows, m_cols);

if (m_rows != m_cols)

return adj;

cofactor = this->CoFactor();

// adjoint is transpose of a cofactor of a matrix

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

adj.m_pData[j][i] = cofactor.m_pData[i][j];

}

return adj;

}

CMatrix Transpose()

{

CMatrix trans("TR", m_cols, m_rows);

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

trans.m_pData[j][i] = m_pData[i][j];

}

return trans;

}

CMatrix Inverse()

{

CMatrix cofactor("COF", m_rows, m_cols);

CMatrix inv("INV", m_rows, m_cols);

if (m_rows != m_cols)

return inv;

// to find out Determinant

double det = Determinant();

cofactor = this->CoFactor();

// inv = transpose of cofactor / Determinant

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

inv.m_pData[j][i] = cofactor.m_pData[i][j] / det;

}

return inv;

}

CMatrix operator +(const CMatrix &other)

{

if (this->m_rows != other.m_rows || this->m_cols != other.m_cols)

{

std::cout

<< "Addition could not take place because number of rows and columns are different between the two matrices";

return *this;

}

CMatrix result("", m_rows, m_cols);

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

result.m_pData[i][j] = this->m_pData[i][j]

+ other.m_pData[i][j];

}

return result;

}

CMatrix operator -(const CMatrix &other)

{

if (this->m_rows != other.m_rows || this->m_cols != other.m_cols)

{

std::cout

<< "Subtraction could not take place because number of rows and columns are different between the two matrices";

return *this;

}

CMatrix result("", m_rows, m_cols);

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

result.m_pData[i][j] = this->m_pData[i][j]

- other.m_pData[i][j];

}

return result;

}

CMatrix operator *(const CMatrix &other)

{

if (this->m_cols != other.m_rows)

{

std::cout

<< "Multiplication could not take place because number of columns of 1st Matrix and number of rows in 2nd Matrix are different";

return *this;

}

CMatrix result("", this->m_rows, other.m_cols);

for (int i = 0; i < this->m_rows; i++)

{

for (int j = 0; j < other.m_cols; j++)

{

for (int k = 0; k < this->m_cols; k++)

{

result.m_pData[i][j] += this->m_pData[i][k]

* other.m_pData[k][j];

}

return result;

}

bool operator ==(const CMatrix &other)

{

if (this->m_rows != other.m_rows || this->m_cols != other.m_cols)

{

std::cout

<< "Comparision could not take place because number of rows and columns are different between the two matrices";

return false;

}

CMatrix result("", m_rows, m_cols);

bool bEqual = true;

for (int i = 0; i < m_rows; i++)

{

for (int j = 0; j < m_cols; j++)

{

if (this->m_pData[i][j] != other.m_pData[i][j])

bEqual = false;

}

return bEqual;

}

friend std::istream& operator >>(std::istream &is, CMatrix &m);

friend std::ostream& operator <<(std::ostream &os, const CMatrix &m);

};

std::istream& operator >>(std::istream &is, CMatrix &m)

{

std::cout << "\n\nEnter Input For Matrix : " << m.m_name << " Rows: "

<< m.m_rows << " Cols: " << m.m_cols << "\n";

for (int i = 0; i < m.m_rows; i++)

{

for (int j = 0; j < m.m_cols; j++)

{

std::cout << "Input For Row: " << i + 1 << " Col: " << j + 1

<< " = ";

is >> m.m_pData[i][j];

}

std::cout << "\n";

}

std::cout << "\n";

return is;

}

std::ostream& operator <<(std::ostream &os, const CMatrix &m)

{

os << "\n\nMatrix : " << m.m_name << " Rows: " << m.m_rows << " Cols: "

<< m.m_cols << "\n\n";

for (int i = 0; i < m.m_rows; i++)

{

os << " | ";

for (int j = 0; j < m.m_cols; j++)

{

char buf[32];

double data = m.m_pData[i][j];

if (m.m_pData[i][j] > -0.00001 && m.m_pData[i][j] < 0.00001)

data = 0;

sprintf(buf, "%10.2lf ", data);

os << buf;

}

os << "|\n";

}

os << "\n\n";

return os;

}

#endif

int main()

{

CMatrix a("A", 5, 5);

//std::cin >> a;

a.FillSimulatedInput();

CMatrix aadj = a.Inverse();

std::cout << a;

std::cout << aadj;

CMatrix unit = (a * aadj);

unit.SetName("A * A-Inv");

std::cout << unit;

}

OUTPUT:



$ g++ InverseOfMatrix.cpp
$ a.out
 
Enter Input For Matrix : 
A Rows: 5 
Cols: 5
Input For Row: 1 Col: 1 = 0.294118
Input For Row: 1 Col: 2 = 0.980392
Input For Row: 1 Col: 3 = 1.86275
Input For Row: 1 Col: 4 = 2.84314
Input For Row: 1 Col: 5 = 3.62745
 
Input For Row: 2 Col: 1 = 2.54902
Input For Row: 2 Col: 2 = 3.92157
Input For Row: 2 Col: 3 = 5.09804
Input For Row: 2 Col: 4 = 7.05882
Input For Row: 2 Col: 5 = 9.80392
 
Input For Row: 3 Col: 1 = 6.66667
Input For Row: 3 Col: 2 = 8.92157
Input For Row: 3 Col: 3 = 10.8824
Input For Row: 3 Col: 4 = 12.6471
Input For Row: 3 Col: 5 = 15.3922
 
Input For Row: 4 Col: 1 = 12.0588
Input For Row: 4 Col: 2 = 15.098
Input For Row: 4 Col: 3 = 18.1373
Input For Row: 4 Col: 4 = 20.7843
Input For Row: 4 Col: 5 = 24.4118
 
Input For Row: 5 Col: 1 = 21.1765
Input For Row: 5 Col: 2 = 24.7059
Input For Row: 5 Col: 3 = 27.7451
Input For Row: 5 Col: 4 = 31.0784
Input For Row: 5 Col: 5 = 34.3137
 
Matrix : A Rows: 5 Cols: 5
 
 |       0.29       0.98       1.86       2.84       3.63 |
 |       2.55       3.92       5.10       7.06       9.80 |
 |       6.67       8.92      10.88      12.65      15.39 |
 |      12.06      15.10      18.14      20.78      24.41 |
 |      21.18      24.71      27.75      31.08      34.31 |
 
Matrix : INV Rows: 5 Cols: 5
 
 |      -0.93       0.80      -3.74       2.86      -0.49 |
 |       0.37      -0.32       5.35      -4.91       1.14 |
 |      -0.78      -0.93      -1.46       2.96      -1.10 |
 |       2.37      -0.10       0.25      -1.65       0.84 |
 |      -1.21       0.57      -0.58       0.87      -0.36 |
 
Matrix : A * A-Inv Rows: 5 Cols: 5
 
 |       1.00       0.00       0.00       0.00       0.00 |
 |       0.00       1.00       0.00       0.00       0.00 |
 |       0.00       0.00       1.00       0.00       0.00 |
 |       0.00       0.00       0.00       1.00       0.00 |
 |       0.00       0.00       0.00       0.00       1.00 |

$ g++ InverseOfMatrix.cpp

$ a.out

Enter Input For Matrix :

A Rows: 5

Cols: 5

Input For Row: 1 Col: 1 = 0.294118

Input For Row: 1 Col: 2 = 0.980392

Input For Row: 1 Col: 3 = 1.86275

Input For Row: 1 Col: 4 = 2.84314

Input For Row: 1 Col: 5 = 3.62745

Input For Row: 2 Col: 1 = 2.54902

Input For Row: 2 Col: 2 = 3.92157

Input For Row: 2 Col: 3 = 5.09804

Input For Row: 2 Col: 4 = 7.05882

Input For Row: 2 Col: 5 = 9.80392

Input For Row: 3 Col: 1 = 6.66667

Input For Row: 3 Col: 2 = 8.92157

Input For Row: 3 Col: 3 = 10.8824

Input For Row: 3 Col: 4 = 12.6471

Input For Row: 3 Col: 5 = 15.3922

Input For Row: 4 Col: 1 = 12.0588

Input For Row: 4 Col: 2 = 15.098

Input For Row: 4 Col: 3 = 18.1373

Input For Row: 4 Col: 4 = 20.7843

Input For Row: 4 Col: 5 = 24.4118

Input For Row: 5 Col: 1 = 21.1765

Input For Row: 5 Col: 2 = 24.7059

Input For Row: 5 Col: 3 = 27.7451

Input For Row: 5 Col: 4 = 31.0784

Input For Row: 5 Col: 5 = 34.3137

Matrix : A Rows: 5 Cols: 5

| 0.29 0.98 1.86 2.84 3.63 |

| 2.55 3.92 5.10 7.06 9.80 |

| 6.67 8.92 10.88 12.65 15.39 |

| 12.06 15.10 18.14 20.78 24.41 |

| 21.18 24.71 27.75 31.08 34.31 |

Matrix : INV Rows: 5 Cols: 5

| -0.93 0.80 -3.74 2.86 -0.49 |

| 0.37 -0.32 5.35 -4.91 1.14 |

| -0.78 -0.93 -1.46 2.96 -1.10 |

| 2.37 -0.10 0.25 -1.65 0.84 |

| -1.21 0.57 -0.58 0.87 -0.36 |

Matrix : A * A-Inv Rows: 5 Cols: 5

| 1.00 0.00 0.00 0.00 0.00 |

| 0.00 1.00 0.00 0.00 0.00 |

| 0.00 0.00 1.00 0.00 0.00 |

| 0.00 0.00 0.00 1.00 0.00 |

| 0.00 0.00 0.00 0.00 1.00 |

C++ Program to generate CAPTCHA and verify user

What is CAPTCHA?

A CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a test to determine whether the user is human or not.

So, the task is to generate unique CAPTCHA every time and to tell whether the user is human or not by asking user to enter the same CAPTCHA as generated automatically and checking the user input with the generated CAPTCHA.

So before writing a c++ program to generate CAPTCHA we must understand with the help of example.

Examples:



CAPTCHA: x9Pm72se
Input: x9Pm62es
Output: CAPTCHA Not Matched

CAPTCHA: cF3yl9T4
Input: cF3yl9T4
Output: CAPTCHA Matched

CAPTCHA: x9Pm72se

Input: x9Pm62es

Output: CAPTCHA Not Matched

CAPTCHA: cF3yl9T4

Input: cF3yl9T4

Output: CAPTCHA Matched

The set of characters to generate CAPTCHA are stored in a character array chrs[] which contains (a-z, A-Z, 0-9), therefore size of chrs[] is 62.

To generate a unique CAPTCHA every time, a random number is generated using rand() function (rand()%62) which generates a random number between 0 to 61 and the generated random number is taken as index to the character array chrs[] thus generates a new character of captcha[] and this loop runs n (length of CAPTCHA) times to generate CAPTCHA of given length. Let’s write a C++ program to generate CAPTCHA

C++ program to generate CAPTCHA and verify user:



; title: ; notranslate  ]// C++ program to automatically generate CAPTCHA and
// verify user
#include<bits/stdc++.h>
using namespace std;

// Returns true if given two strings are same
bool checkCaptcha(string &captcha, string &user_captcha)
{
    return captcha.compare(user_captcha) == 0;
}

// Generates a CAPTCHA of given length
string generateCaptcha(int n)
{
    time_t t;
    srand((unsigned)time(&t));

    // Characters to be included
    char *chrs = "abcdefghijklmnopqrstuvwxyzABCDEFGHI"
                  "JKLMNOPQRSTUVWXYZ0123456789";

    // Generate n characters from above set and
    // add these characters to captcha.
    string captcha = "";
    while (n--)
        captcha.push_back(chrs[rand()%62]);

    return captcha;
}

// Driver code
int main()
{
    // Generate a random CAPTCHA
    string captcha = generateCaptcha(9);
    cout << captcha;

    // Ask user to enter a CAPTCHA
    string usr_captcha;
    cout << "nEnter above CAPTCHA: ";
    cin >> usr_captcha;

    // Notify user about matching status
    if (checkCaptcha(captcha, usr_captcha))
        printf("nCAPTCHA Matched");
    else
        printf("nCAPTCHA Not Matched");

    return 0;
}

; title: ; notranslate ]// C++ program to automatically generate CAPTCHA and

// verify user

#include<bits/stdc++.h>

using namespace std;

// Returns true if given two strings are same

bool checkCaptcha(string &captcha, string &user_captcha)

{

return captcha.compare(user_captcha) == 0;

}

// Generates a CAPTCHA of given length

string generateCaptcha(int n)

{

time_t t;

srand((unsigned)time(&t));

// Characters to be included

char *chrs = "abcdefghijklmnopqrstuvwxyzABCDEFGHI"

"JKLMNOPQRSTUVWXYZ0123456789";

// Generate n characters from above set and

// add these characters to captcha.

string captcha = "";

while (n--)

captcha.push_back(chrs[rand()%62]);

return captcha;

}

// Driver code

int main()

{

// Generate a random CAPTCHA

string captcha = generateCaptcha(9);

cout << captcha;

// Ask user to enter a CAPTCHA

string usr_captcha;

cout << "nEnter above CAPTCHA: ";

cin >> usr_captcha;

// Notify user about matching status

if (checkCaptcha(captcha, usr_captcha))

printf("nCAPTCHA Matched");

else

printf("nCAPTCHA Not Matched");

return 0;

}

Output:



CAPTCHA: cF3yl9T4
Enter CAPTCHA: cF3yl9T4
CAPTCHA Matched

CAPTCHA: cF3yl9T4

Enter CAPTCHA: cF3yl9T4

CAPTCHA Matched

Hope you like it easy, please comment if you face any problem.

Method overloading vs Method Overriding

Difference between Method Overloading vs Method overriding:

Overloading can occur without inheritance. Overriding of functions occurs when one class is inherited from another class.

Overloaded functions must differ in function signature i.e. either number of parameters or type of parameters should differ. In overriding, function signatures must be same.

Overloaded functions are in same scope; whereas Overridden functions are in different scopes.

	Method Overloading	Method Overriding
Definition	In Method Overloading, Methods of the same class shares the same name but each method must have different number of parameters or parameters having different types and order.	In Method Overriding, sub class have the same method with same name and exactly the same number and type of parameters and same return type as a super class.
Meaning	Method Overloading means more than one method shares the same name in the class but having different signature.	Method Overriding means method of base class is re-defined in the derived class having same signature.
Behavior	Method Overloading is to “add” or “extend” more to method’s behavior.	Method Overriding is to “Change” existing behavior of method.
Polymorphism	It is a compile time polymorphism.	It is a run time polymorphism.
Inheritance	It may or may not need inheritance in Method Overloading.	It always requires inheritance in Method Overriding.
Signature	In Method Overloading, methods must have different signature.	In Method Overriding, methods must have same signature.
Relationship of Methods	In Method Overloading, relationship is there between methods of same class.	In Method Overriding, relationship is there between methods of super class and sub class.
Criteria	In Method Overloading, methods have same name different signatures but in the same class.	In Method Overriding, methods have same name and same signature but in the different class.
No. of Classes	Method Overloading does not require more than one class for overloading.	Method Overriding requires at least two classes for overriding.

Diagram to understand exact difference :-

Example in program:-

Method Overloading:



Class Add
{
   int sum(int a, int b)
   {
     return a + b;
   }
  int sum(int a)
  {
    return a + 10;
   }
}

Class Add

{

int sum(int a, int b)

{

return a + b;

}

int sum(int a)

{

return a + 10;

}

Method Overriding:



Class A  // Super Class
{
  void display(int num)
  {
     print num ;
   }
}
//Class B inherits Class A
Class B //Sub Class
{
  void display(int num)
  {
     print num ;
   }
}

Class A // Super Class

{

void display(int num)

{

print num ;

}

//Class B inherits Class A

Class B //Sub Class

{

void display(int num)

{

print num ;

}

Red Black-Tree(RB-Tree) implementation in C++

Red Black-Tree (RB-Tree):

A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. It has following properties:

Every node is either red or black.
Every leaf (NULL) is black.
If a node is red, then both its children are black.
Every simple path from a node to a descendant leaf contains the same number of black nodes.

C++ program to implement RB-Tree:



#include<iostream>

using namespace std;

struct node
{
       int key;
       node *parent;
       char color;
       node *left;
       node *right;
};
class RBtree
{
      node *root;
      node *q;
   public :
      RBtree()
      {
              q=NULL;
              root=NULL;
      }
      void insert();
      void insertfix(node *);
      void leftrotate(node *);
      void rightrotate(node *);
      void del();
      node* successor(node *);
      void delfix(node *);
      void disp();
      void display( node *);
      void search();
};
void RBtree::insert()
{
     int z,i=0;
     cout<<"\nEnter key of the node to be inserted: "; cin>>z;
     node *p,*q;
     node *t=new node;
     t->key=z;
     t->left=NULL;
     t->right=NULL;
     t->color='r';
     p=root;
     q=NULL;
     if(root==NULL)
     {
           root=t;
           t->parent=NULL;
     }
     else
     {
         while(p!=NULL)
         {
              q=p;
              if(p->key<t->key)
                  p=p->right;
              else
                  p=p->left;
         }
         t->parent=q;
         if(q->key<t->key)
              q->right=t;
         else
              q->left=t;
     }
     insertfix(t);
}
void RBtree::insertfix(node *t)
{
     node *u;
     if(root==t)
     {
         t->color='b';
         return;
     }
     while(t->parent!=NULL&&t->parent->color=='r')
     {
           node *g=t->parent->parent;
           if(g->left==t->parent)
           {
                        if(g->right!=NULL)
                        {
                              u=g->right;
                              if(u->color=='r')
                              {
                                   t->parent->color='b';
                                   u->color='b';
                                   g->color='r';
                                   t=g;
                              }
                        }
                        else
                        {
                            if(t->parent->right==t)
                            {
                                 t=t->parent;
                                 leftrotate(t);
                            }
                            t->parent->color='b';
                            g->color='r';
                            rightrotate(g);
                        }
           }
           else
           {
                        if(g->left!=NULL)
                        {
                             u=g->left;
                             if(u->color=='r')
                             {
                                  t->parent->color='b';
                                  u->color='b';
                                  g->color='r';
                                  t=g;
                             }
                        }
                        else
                        {
                            if(t->parent->left==t)
                            {
                                   t=t->parent;
                                   rightrotate(t);
                            }
                            t->parent->color='b';
                            g->color='r';
                            leftrotate(g);
                        }
           }
           root->color='b';
     }
}

void RBtree::del()
{
     if(root==NULL)
     {
           cout<<"\nEmpty Tree." ;
           return ;
     }
     int x;
     cout<<"\nEnter the key of the node to be deleted: "; cin>>x;
     node *p;
     p=root;
     node *y=NULL;
     node *q=NULL;
     int found=0;
     while(p!=NULL&&found==0)
     {
           if(p->key==x)
               found=1;
           if(found==0)
           {
                 if(p->key<x) p=p->right;
                 else
                    p=p->left;
           }
     }
     if(found==0)
     {
            cout<<"\nElement Not Found.";
            return ;
     }
     else
     {
         cout<<"\nDeleted Element: "<<p->key;
         cout<<"\nColour: "; if(p->color=='b')
     cout<<"Black\n";
    else
     cout<<"Red\n"; if(p->parent!=NULL)
               cout<<"\nParent: "<<p->parent->key;
         else
               cout<<"\nThere is no parent of the node. "; if(p->right!=NULL)
               cout<<"\nRight Child: "<<p->right->key;
         else
               cout<<"\nThere is no right child of the node. "; if(p->left!=NULL)
               cout<<"\nLeft Child: "<<p->left->key;
         else
               cout<<"\nThere is no left child of the node.  ";
         cout<<"\nNode Deleted."; if(p->left==NULL||p->right==NULL)
              y=p;
         else
              y=successor(p);
         if(y->left!=NULL)
              q=y->left;
         else
         {
              if(y->right!=NULL)
                   q=y->right;
              else
                   q=NULL;
         }
         if(q!=NULL)
              q->parent=y->parent;
         if(y->parent==NULL)
              root=q;
         else
         {
             if(y==y->parent->left)
                y->parent->left=q;
             else
                y->parent->right=q;
         }
         if(y!=p)
         {
             p->color=y->color;
             p->key=y->key;
         }
         if(y->color=='b')
             delfix(q);
     }
}

void RBtree::delfix(node *p)
{
    node *s;
    while(p!=root&&p->color=='b')
    {
          if(p->parent->left==p)
          {
                  s=p->parent->right;
                  if(s->color=='r')
                  {
                         s->color='b';
                         p->parent->color='r';
                         leftrotate(p->parent);
                         s=p->parent->right;
                  }
                  if(s->right->color=='b'&&s->left->color=='b')
                  {
                         s->color='r';
                         p=p->parent;
                  }
                  else
                  {
                      if(s->right->color=='b')
                      {
                             s->left->color=='b';
                             s->color='r';
                             rightrotate(s);
                             s=p->parent->right;
                      }
                      s->color=p->parent->color;
                      p->parent->color='b';
                      s->right->color='b';
                      leftrotate(p->parent);
                      p=root;
                  }
          }
          else
          {
                  s=p->parent->left;
                  if(s->color=='r')
                  {
                        s->color='b';
                        p->parent->color='r';
                        rightrotate(p->parent);
                        s=p->parent->left;
                  }
                  if(s->left->color=='b'&&s->right->color=='b')
                  {
                        s->color='r';
                        p=p->parent;
                  }
                  else
                  {
                        if(s->left->color=='b')
                        {
                              s->right->color='b';
                              s->color='r';
                              leftrotate(s);
                              s=p->parent->left;
                        }
                        s->color=p->parent->color;
                        p->parent->color='b';
                        s->left->color='b';
                        rightrotate(p->parent);
                        p=root;
                  }
          }
       p->color='b';
       root->color='b';
    }
}

void RBtree::leftrotate(node *p)
{
     if(p->right==NULL)
           return ;
     else
     {
           node *y=p->right;
           if(y->left!=NULL)
           {
                  p->right=y->left;
                  y->left->parent=p;
           }
           else
                  p->right=NULL;
           if(p->parent!=NULL)
                y->parent=p->parent;
           if(p->parent==NULL)
                root=y;
           else
           {
               if(p==p->parent->left)
                       p->parent->left=y;
               else
                       p->parent->right=y;
           }
           y->left=p;
           p->parent=y;
     }
}
void RBtree::rightrotate(node *p)
{
     if(p->left==NULL)
          return ;
     else
     {
         node *y=p->left;
         if(y->right!=NULL)
         {
                  p->left=y->right;
                  y->right->parent=p;
         }
         else
                 p->left=NULL;
         if(p->parent!=NULL)
                 y->parent=p->parent;
         if(p->parent==NULL)
               root=y;
         else
         {
             if(p==p->parent->left)
                   p->parent->left=y;
             else
                   p->parent->right=y;
         }
         y->right=p;
         p->parent=y;
     }
}

node* RBtree::successor(node *p)
{
      node *y=NULL;
     if(p->left!=NULL)
     {
         y=p->left;
         while(y->right!=NULL)
              y=y->right;
     }
     else
     {
         y=p->right;
         while(y->left!=NULL)
              y=y->left;
     }
     return y;
}

void RBtree::disp()
{
     display(root);
}
void RBtree::display(node *p)
{
     if(root==NULL)
     {
          cout<<"\nEmpty Tree.";
          return ;
     }
     if(p!=NULL)
     {
                cout<<"\n\t NODE: ";
                cout<<"\n Key: "<<p->key;
                cout<<"\n Colour: "; if(p->color=='b')
     cout<<"Black";
    else
     cout<<"Red"; if(p->parent!=NULL)
                       cout<<"\n Parent: "<<p->parent->key;
                else
                       cout<<"\n There is no parent of the node. "; if(p->right!=NULL)
                       cout<<"\n Right Child: "<<p->right->key;
                else
                       cout<<"\n There is no right child of the node. "; if(p->left!=NULL)
                       cout<<"\n Left Child: "<<p->left->key;
                else
                       cout<<"\n There is no left child of the node.  ";
                cout<<endl; if(p->left)
    {
                 cout<<"\n\nLeft:\n"; display(p->left);
    }
    /*else
     cout<<"\nNo Left Child.\n";*/ if(p->right)
    {
     cout<<"\n\nRight:\n"; display(p->right);
    }
    /*else
     cout<<"\nNo Right Child.\n"*/
     }
}
void RBtree::search()
{
     if(root==NULL)
     {
           cout<<"\nEmpty Tree\n" ;
           return  ;
     }
     int x;
     cout<<"\n Enter key of the node to be searched: "; cin>>x;
     node *p=root;
     int found=0;
     while(p!=NULL&& found==0)
     {
            if(p->key==x)
                found=1;
            if(found==0)
            {
                 if(p->key<x) p=p->right;
                 else
                      p=p->left;
            }
     }
     if(found==0)
          cout<<"\nElement Not Found.";
     else
     {
                cout<<"\n\t FOUND NODE: ";
                cout<<"\n Key: "<<p->key;
                cout<<"\n Colour: "; if(p->color=='b')
     cout<<"Black";
    else
     cout<<"Red"; if(p->parent!=NULL)
                       cout<<"\n Parent: "<<p->parent->key;
                else
                       cout<<"\n There is no parent of the node. "; if(p->right!=NULL)
                       cout<<"\n Right Child: "<<p->right->key;
                else
                       cout<<"\n There is no right child of the node. "; if(p->left!=NULL)
                       cout<<"\n Left Child: "<<p->left->key;
                else
                       cout<<"\n There is no left child of the node.  ";
                cout<<endl;

     }
}
int main()
{
    int ch,y=0;
    RBtree obj;
    do
    {
                cout<<"\n\t RED BLACK TREE " ;
                cout<<"\n 1. Insert in the tree ";
                cout<<"\n 2. Delete a node from the tree";
                cout<<"\n 3. Search for an element in the tree";
                cout<<"\n 4. Display the tree ";
                cout<<"\n 5. Exit " ;
                cout<<"\nEnter Your Choice: "; cin>>ch;
                switch(ch)
                {
                          case 1 : obj.insert();
                                   cout<<"\nNode Inserted.\n";
                                   break;
                          case 2 : obj.del();
                                   break;
                          case 3 : obj.search();
                                   break;
                          case 4 : obj.disp();
                                   break;
                          case 5 : y=1;
                                   break;
                          default : cout<<"\nEnter a Valid Choice.";
                }
                cout<<endl;

    }while(y!=1);
    return 1;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

#include<iostream>

using namespace std;

struct node

{

int key;

node *parent;

char color;

node *left;

node *right;

};

class RBtree

{

node *root;

node *q;

public :

RBtree()

{

q=NULL;

root=NULL;

}

void insert();

void insertfix(node *);

void leftrotate(node *);

void rightrotate(node *);

void del();

node* successor(node *);

void delfix(node *);

void disp();

void display( node *);

void search();

};

void RBtree::insert()

{

int z,i=0;

cout<<"\nEnter key of the node to be inserted: "; cin>>z;

node *p,*q;

node *t=new node;

t->key=z;

t->left=NULL;

t->right=NULL;

t->color='r';

p=root;

q=NULL;

if(root==NULL)

{

root=t;

t->parent=NULL;

}

else

{

while(p!=NULL)

{

q=p;

if(p->key<t->key)

p=p->right;

else

p=p->left;

}

t->parent=q;

if(q->key<t->key)

q->right=t;

else

q->left=t;

}

insertfix(t);

}

void RBtree::insertfix(node *t)

{

node *u;

if(root==t)

{

t->color='b';

return;

}

while(t->parent!=NULL&&t->parent->color=='r')

{

node *g=t->parent->parent;

if(g->left==t->parent)

{

if(g->right!=NULL)

{

u=g->right;

if(u->color=='r')

{

t->parent->color='b';

u->color='b';

g->color='r';

t=g;

}

else

{

if(t->parent->right==t)

{

t=t->parent;

leftrotate(t);

}

t->parent->color='b';

g->color='r';

rightrotate(g);

}

else

{

if(g->left!=NULL)

{

u=g->left;

if(u->color=='r')

{

t->parent->color='b';

u->color='b';

g->color='r';

t=g;

}

else

{

if(t->parent->left==t)

{

t=t->parent;

rightrotate(t);

}

t->parent->color='b';

g->color='r';

leftrotate(g);

}

root->color='b';

}

void RBtree::del()

{

if(root==NULL)

{

cout<<"\nEmpty Tree." ;

return ;

}

int x;

cout<<"\nEnter the key of the node to be deleted: "; cin>>x;

node *p;

p=root;

node *y=NULL;

node *q=NULL;

int found=0;

while(p!=NULL&&found==0)

{

if(p->key==x)

found=1;

if(found==0)

{

if(p->key<x) p=p->right;

else

p=p->left;

}

if(found==0)

{

cout<<"\nElement Not Found.";

return ;

}

else

{

cout<<"\nDeleted Element: "<<p->key;

cout<<"\nColour: "; if(p->color=='b')

cout<<"Black\n";

else

cout<<"Red\n"; if(p->parent!=NULL)

cout<<"\nParent: "<<p->parent->key;

else

cout<<"\nThere is no parent of the node. "; if(p->right!=NULL)

cout<<"\nRight Child: "<<p->right->key;

else

cout<<"\nThere is no right child of the node. "; if(p->left!=NULL)

cout<<"\nLeft Child: "<<p->left->key;

else

cout<<"\nThere is no left child of the node. ";

cout<<"\nNode Deleted."; if(p->left==NULL||p->right==NULL)

y=p;

else

y=successor(p);

if(y->left!=NULL)

q=y->left;

else

{

if(y->right!=NULL)

q=y->right;

else

q=NULL;

}

if(q!=NULL)

q->parent=y->parent;

if(y->parent==NULL)

root=q;

else

{

if(y==y->parent->left)

y->parent->left=q;

else

y->parent->right=q;

}

if(y!=p)

{

p->color=y->color;

p->key=y->key;

}

if(y->color=='b')

delfix(q);

}

void RBtree::delfix(node *p)

{

node *s;

while(p!=root&&p->color=='b')

{

if(p->parent->left==p)

{

s=p->parent->right;

if(s->color=='r')

{

s->color='b';

p->parent->color='r';

leftrotate(p->parent);

s=p->parent->right;

}

if(s->right->color=='b'&&s->left->color=='b')

{

s->color='r';

p=p->parent;

}

else

{

if(s->right->color=='b')

{

s->left->color=='b';

s->color='r';

rightrotate(s);

s=p->parent->right;

}

s->color=p->parent->color;

p->parent->color='b';

s->right->color='b';

leftrotate(p->parent);

p=root;

}

else

{

s=p->parent->left;

if(s->color=='r')

{

s->color='b';

p->parent->color='r';

rightrotate(p->parent);

s=p->parent->left;

}

if(s->left->color=='b'&&s->right->color=='b')

{

s->color='r';

p=p->parent;

}

else

{

if(s->left->color=='b')

{

s->right->color='b';

s->color='r';

leftrotate(s);

s=p->parent->left;

}

s->color=p->parent->color;

p->parent->color='b';

s->left->color='b';

rightrotate(p->parent);

p=root;

}

p->color='b';

root->color='b';

}

void RBtree::leftrotate(node *p)

{

if(p->right==NULL)

return ;

else

{

node *y=p->right;

if(y->left!=NULL)

{

p->right=y->left;

y->left->parent=p;

}

else

p->right=NULL;

if(p->parent!=NULL)

y->parent=p->parent;

if(p->parent==NULL)

root=y;

else

{

if(p==p->parent->left)

p->parent->left=y;

else

p->parent->right=y;

}

y->left=p;

p->parent=y;

}

void RBtree::rightrotate(node *p)

{

if(p->left==NULL)

return ;

else

{

node *y=p->left;

if(y->right!=NULL)

{

p->left=y->right;

y->right->parent=p;

}

else

p->left=NULL;

if(p->parent!=NULL)

y->parent=p->parent;

if(p->parent==NULL)

root=y;

else

{

if(p==p->parent->left)

p->parent->left=y;

else

p->parent->right=y;

}

y->right=p;

p->parent=y;

}

node* RBtree::successor(node *p)

{

node *y=NULL;

if(p->left!=NULL)

{

y=p->left;

while(y->right!=NULL)

y=y->right;

}

else

{

y=p->right;

while(y->left!=NULL)

y=y->left;

}

return y;

}

void RBtree::disp()

{

display(root);

}

void RBtree::display(node *p)

{

if(root==NULL)

{

cout<<"\nEmpty Tree.";

return ;

}

if(p!=NULL)

{

cout<<"\n\t NODE: ";

cout<<"\n Key: "<<p->key;

cout<<"\n Colour: "; if(p->color=='b')

cout<<"Black";

else

cout<<"Red"; if(p->parent!=NULL)

cout<<"\n Parent: "<<p->parent->key;

else

cout<<"\n There is no parent of the node. "; if(p->right!=NULL)

cout<<"\n Right Child: "<<p->right->key;

else

cout<<"\n There is no right child of the node. "; if(p->left!=NULL)

cout<<"\n Left Child: "<<p->left->key;

else

cout<<"\n There is no left child of the node. ";

cout<<endl; if(p->left)

{

cout<<"\n\nLeft:\n"; display(p->left);

}

/*else

cout<<"\nNo Left Child.\n";*/ if(p->right)

{

cout<<"\n\nRight:\n"; display(p->right);

}

/*else

cout<<"\nNo Right Child.\n"*/

}

void RBtree::search()

{

if(root==NULL)

{

cout<<"\nEmpty Tree\n" ;

return ;

}

int x;

cout<<"\n Enter key of the node to be searched: "; cin>>x;

node *p=root;

int found=0;

while(p!=NULL&& found==0)

{

if(p->key==x)

found=1;

if(found==0)

{

if(p->key<x) p=p->right;

else

p=p->left;

}

if(found==0)

cout<<"\nElement Not Found.";

else

{

cout<<"\n\t FOUND NODE: ";

cout<<"\n Key: "<<p->key;

cout<<"\n Colour: "; if(p->color=='b')

cout<<"Black";

else

cout<<"Red"; if(p->parent!=NULL)

cout<<"\n Parent: "<<p->parent->key;

else

cout<<"\n There is no parent of the node. "; if(p->right!=NULL)

cout<<"\n Right Child: "<<p->right->key;

else

cout<<"\n There is no right child of the node. "; if(p->left!=NULL)

cout<<"\n Left Child: "<<p->left->key;

else

cout<<"\n There is no left child of the node. ";

cout<<endl;

}

int main()

{

int ch,y=0;

RBtree obj;

{

cout<<"\n\t RED BLACK TREE " ;

cout<<"\n 1. Insert in the tree ";

cout<<"\n 2. Delete a node from the tree";

cout<<"\n 3. Search for an element in the tree";

cout<<"\n 4. Display the tree ";

cout<<"\n 5. Exit " ;

cout<<"\nEnter Your Choice: "; cin>>ch;

switch(ch)

{

case 1 : obj.insert();

cout<<"\nNode Inserted.\n";

break;

case 2 : obj.del();

break;

case 3 : obj.search();

break;

case 4 : obj.disp();

break;

case 5 : y=1;

break;

default : cout<<"\nEnter a Valid Choice.";

}

cout<<endl;

}while(y!=1);

return 1;

}

Sample Output



	 RED BLACK TREE 
 1. Insert in the tree 
 2. Delete a node from the tree
 3. Search for an element in the tree
 4. Display the tree 
 5. Exit 
Enter Your Choice: 1

Enter key of the node to be inserted: 4

Node Inserted.


	 RED BLACK TREE 
 1. Insert in the tree 
 2. Delete a node from the tree
 3. Search for an element in the tree
 4. Display the tree 
 5. Exit 
Enter Your Choice: 1

Enter key of the node to be inserted: 15

Node Inserted.


	 RED BLACK TREE 
 1. Insert in the tree 
 2. Delete a node from the tree
 3. Search for an element in the tree
 4. Display the tree 
 5. Exit 
Enter Your Choice: 1

Enter key of the node to be inserted: 8

Node Inserted.


	 RED BLACK TREE 
 1. Insert in the tree 
 2. Delete a node from the tree
 3. Search for an element in the tree
 4. Display the tree 
 5. Exit 
Enter Your Choice: 4

	 NODE: 
 Key: 12
 Colour: Black
 There is no parent of the node.  
 Right Child: 15
 Left Child: 4


Left:

	 NODE: 
 Key: 4
 Colour: Black
 Parent: 12
 Right Child: 8
 There is no left child of the node.  


Right:

	 NODE: 
 Key: 8
 Colour: Red
 Parent: 4
 There is no right child of the node.  
 There is no left child of the node.  


Right:

	 NODE: 
 Key: 15
 Colour: Black
 Parent: 12
 There is no right child of the node.  
 There is no left child of the node.  


	 RED BLACK TREE 
 1. Insert in the tree 
 2. Delete a node from the tree
 3. Search for an element in the tree
 4. Display the tree 
 5. Exit 
Enter Your Choice: 5

RED BLACK TREE

1. Insert in the tree

2. Delete a node from the tree

3. Search for an element in the tree

4. Display the tree

5. Exit

Enter Your Choice: 1

Enter key of the node to be inserted: 4

Node Inserted.

RED BLACK TREE

1. Insert in the tree

2. Delete a node from the tree

3. Search for an element in the tree

4. Display the tree

5. Exit

Enter Your Choice: 1

Enter key of the node to be inserted: 15

Node Inserted.

RED BLACK TREE

1. Insert in the tree

2. Delete a node from the tree

3. Search for an element in the tree

4. Display the tree

5. Exit

Enter Your Choice: 1

Enter key of the node to be inserted: 8

Node Inserted.

RED BLACK TREE

1. Insert in the tree

2. Delete a node from the tree

3. Search for an element in the tree

4. Display the tree

5. Exit

Enter Your Choice: 4

NODE:

Key: 12

Colour: Black

There is no parent of the node.

Right Child: 15

Left Child: 4

Left:

NODE:

Key: 4

Colour: Black

Parent: 12

Right Child: 8

There is no left child of the node.

Right:

NODE:

Key: 8

Colour: Red

Parent: 4

There is no right child of the node.

There is no left child of the node.

Right:

NODE:

Key: 15

Colour: Black

Parent: 12

There is no right child of the node.

There is no left child of the node.

RED BLACK TREE

1. Insert in the tree

2. Delete a node from the tree

3. Search for an element in the tree

4. Display the tree

5. Exit

Enter Your Choice: 5

Implement function overloading to find Area of Shapes

What is Function Overloading?

When we define one function with more than one definition it is known as Function overloading. For example:



int shape(int x);

int shape(int x, int y);

int shape(int x);

int shape(int x, int y);

We can have multiple definitions for the same function name in the same scope. The definition of the function must differ from each other by the types and/or the number of arguments in the argument list. We can not overload function declarations that differ only by return type.

Program to implement Function Overloading to find area of different shapes:



#include <iostream>

using namespace std;
class measure
{
    public:
        void shape(int r);
        void shape(int l,int b);
        void shape(float t,int d,int e);
        void shape(long a);
        void shape(float c, long int g);
        void shape(double j);
        void shape(float h, double f);
};
void measure::shape(int r)
{
    cout<<"area of the circle is "<<3.14*r*r;
}
void measure::shape(int l,int b)
{
    cout<<"area of the rectangle is "<<l*b;
}
void measure::shape(float t,int d,int e)
{
    cout<<"area of the triangle is "<<t*d*e;
}
void measure::shape(long a)
{
    cout<<"area of the square is "<<a*a;
}
void measure::shape(float c, long int g)
{
    cout<<"Volume of the cone is "<<((3.14*c*c*g)/3);
}
void measure::shape(double j)
{
    cout<<"Volume of the sphere is "<<(4/3)*3.14*j*j*j;
}
void measure::shape(float h, double f)
{
    cout<<"nVolume of the Cylinder is "<<3.14*f*f*h;
}
int main()
{
    char choice;
    int r,d,e,l,b;
    float t,c,h;
    long a;
    int ch;
    double j,f;
    long int g;
    measure obj;
    do
    {
        cout<<"tImplement Function Overloading";
        cout<<"nn1. area of circle";
        cout<<"n2. area of rectangle";
        cout<<"n3. area of triangle";
        cout<<"n4. area of square";
        cout<<"n5. Volume of the cone";
        cout<<"n6. Volume of the sphere";
        cout<<"n7. Volume of the cylinder";
        cout<<"ntEnter your choice ";
        cin>>ch;

        switch(ch)
        {
            case 1:
                cout<<"enter the value of radius of the circle n";
                cin>>r;
                obj.shape(r);
                break;
            case 2:
                cout<<"enter the sides of rectangle n";
                cin>>l>>b;
                obj.shape(l,b);
                break;
            case 3:
                cout<<"enter the sides of triangle n";
                cin>>d>>e;
                obj.shape(0.5,d,e);
                break;
            case 4:
                cout<<"enter the sides of square ";
                cin>>a;
                obj.shape(a);
                break;
            case 5:
                cout<<"nEnter the radius of the cone ";
                cin>>c;
                cout<<"nEnter the height of the cone ";
                cin>>g;
                obj.shape(c,g);
                break;
            case 6:
                cout<<"nEnter the radius ";
                cin>>b;
                obj.shape(b);
                break;
            case 7:
                cout<<"nEnter the radius ";
                cin>>f;
                cout<<"nEnter the height ";
                cin>>h;
                obj.shape(h,f);
                break;
            default:
                cout<<"nThe choice entered is a wrong choice";
        }
        cout<<"nWant to Continue? (Y/N)";
        cin>>choice;
    }
    while(choice=='Y' || choice == 'y');
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <iostream>

using namespace std;

class measure

{

public:

void shape(int r);

void shape(int l,int b);

void shape(float t,int d,int e);

void shape(long a);

void shape(float c, long int g);

void shape(double j);

void shape(float h, double f);

};

void measure::shape(int r)

{

cout<<"area of the circle is "<<3.14*r*r;

}

void measure::shape(int l,int b)

{

cout<<"area of the rectangle is "<<l*b;

}

void measure::shape(float t,int d,int e)

{

cout<<"area of the triangle is "<<t*d*e;

}

void measure::shape(long a)

{

cout<<"area of the square is "<<a*a;

}

void measure::shape(float c, long int g)

{

cout<<"Volume of the cone is "<<((3.14*c*c*g)/3);

}

void measure::shape(double j)

{

cout<<"Volume of the sphere is "<<(4/3)*3.14*j*j*j;

}

void measure::shape(float h, double f)

{

cout<<"nVolume of the Cylinder is "<<3.14*f*f*h;

}

int main()

{

char choice;

int r,d,e,l,b;

float t,c,h;

long a;

int ch;

double j,f;

long int g;

measure obj;

{

cout<<"tImplement Function Overloading";

cout<<"nn1. area of circle";

cout<<"n2. area of rectangle";

cout<<"n3. area of triangle";

cout<<"n4. area of square";

cout<<"n5. Volume of the cone";

cout<<"n6. Volume of the sphere";

cout<<"n7. Volume of the cylinder";

cout<<"ntEnter your choice ";

cin>>ch;

switch(ch)

{

case 1:

cout<<"enter the value of radius of the circle n";

cin>>r;

obj.shape(r);

break;

case 2:

cout<<"enter the sides of rectangle n";

cin>>l>>b;

obj.shape(l,b);

break;

case 3:

cout<<"enter the sides of triangle n";

cin>>d>>e;

obj.shape(0.5,d,e);

break;

case 4:

cout<<"enter the sides of square ";

cin>>a;

obj.shape(a);

break;

case 5:

cout<<"nEnter the radius of the cone ";

cin>>c;

cout<<"nEnter the height of the cone ";

cin>>g;

obj.shape(c,g);

break;

case 6:

cout<<"nEnter the radius ";

cin>>b;

obj.shape(b);

break;

case 7:

cout<<"nEnter the radius ";

cin>>f;

cout<<"nEnter the height ";

cin>>h;

obj.shape(h,f);

break;

default:

cout<<"nThe choice entered is a wrong choice";

}

cout<<"nWant to Continue? (Y/N)";

cin>>choice;

}

while(choice=='Y' || choice == 'y');

return 0;

}

Sample Output:



   Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 1
enter the value of radius of the circle
13
area of the circle is 530.66
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 2
enter the sides of rectangle
12
8
area of the rectangle is 96
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 3
enter the sides of triangle
6
9
area of the triangle is 27
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 4
enter the sides of square 8
area of the square is 64
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 5

Enter the radius of the cone 12

Enter the height of the cone 4
Volume of the cone is 602.88
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 6

Enter the radius 12
area of the circle is 452.16
Want to Continue? (Y/N)y
    Implement Function Overloading

1. area of circle
2. area of rectangle
3. area of triangle
4. area of square
5. Volume of the cone
6. Volume of the sphere
7. Volume of the cylinder
    Enter your choice 7

Enter the radius 12

Enter the height 4

Volume of the Cylinder is 1808.64
Want to Continue? (Y/N)n

100

101

102

103

104

105

106

107

108

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 1

enter the value of radius of the circle

area of the circle is 530.66

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 2

enter the sides of rectangle

area of the rectangle is 96

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 3

enter the sides of triangle

area of the triangle is 27

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 4

enter the sides of square 8

area of the square is 64

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 5

Enter the radius of the cone 12

Enter the height of the cone 4

Volume of the cone is 602.88

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 6

Enter the radius 12

area of the circle is 452.16

Want to Continue? (Y/N)y

Implement Function Overloading

1. area of circle

2. area of rectangle

3. area of triangle

4. area of square

5. Volume of the cone

6. Volume of the sphere

7. Volume of the cylinder

Enter your choice 7

Enter the radius 12

Enter the height 4

Volume of the Cylinder is 1808.64

Want to Continue? (Y/N)n

Solution for Tower of Hanoi C++

What is Tower of Hanoi?

All must be well aware of the problem of Tower of Hanoi, for those who don’t know, let’s discuss it once again.

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower, and sometimes pluralized) is a mathematical game or puzzle.

tower of hanoi

It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.

Animated Solution:

We can solve it in 2 ways:

Using Recursion
Using Stacks

Using Recursion:



#include <iostream>
using namespace std;

void towers(int, char, char, char);

int main()
{
    int num;

    cout<<"Enter the number of disks : ";
    cin>>num;
    cout<<"The sequence of moves involved in the Tower of Hanoi are :n";
    towers(num, 'A', 'C', 'B');
    return 0;
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {
        cout<<"n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg;
        return;
    }
    towers(num - 1, frompeg, auxpeg, topeg);
    cout<<"n Move disk "<<num<<" from peg "<<frompeg<<" to peg "<<topeg;
    towers(num - 1, auxpeg, topeg, frompeg);
}

#include <iostream>

using namespace std;

void towers(int, char, char, char);

int main()

{

int num;

cout<<"Enter the number of disks : ";

cin>>num;

cout<<"The sequence of moves involved in the Tower of Hanoi are :n";

towers(num, 'A', 'C', 'B');

return 0;

}

void towers(int num, char frompeg, char topeg, char auxpeg)

{

if (num == 1)

{

cout<<"n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg;

return;

}

towers(num - 1, frompeg, auxpeg, topeg);

cout<<"n Move disk "<<num<<" from peg "<<frompeg<<" to peg "<<topeg;

towers(num - 1, auxpeg, topeg, frompeg);

}

Sample Output:



Enter the number of disks : 3
The sequence of moves involved in the Tower of Hanoi are :

 Move disk 1 from peg A to peg C
 Move disk 2 from peg A to peg B
 Move disk 1 from peg C to peg B
 Move disk 3 from peg A to peg C
 Move disk 1 from peg B to peg A
 Move disk 2 from peg B to peg C
 Move disk 1 from peg A to peg C

Enter the number of disks : 3

The sequence of moves involved in the Tower of Hanoi are :

Move disk 1 from peg A to peg C

Move disk 2 from peg A to peg B

Move disk 1 from peg C to peg B

Move disk 3 from peg A to peg C

Move disk 1 from peg B to peg A

Move disk 2 from peg B to peg C

Move disk 1 from peg A to peg C

Program to solve Tower of Hanoi C++ using Stack



#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
struct node1
{
    int data1;
    node1 *next1;
}*top1 = NULL, *p1 = NULL, *np1 = NULL;
struct node2
{
    int data2;
    node2 *next2;
}*top2 = NULL, *p2 = NULL, *np2 = NULL;
struct node3
{
    int data3;
    node3 *next3;
}*top3 = NULL, *p3 = NULL, *np3 = NULL;
void push1(int data)
{
    np1 = new node1;
    np1->data1 = data;
    np1->next1 = NULL;
    if (top1 == NULL)
    {
        top1 = np1;
    }
    else
    {
        np1->next1 = top1;
        top1 = np1;
    }
}
int pop1()
{
    int b = 999;
    if (top1 == NULL)
    {
        return b;
    }
    else
    {
        p1 = top1;
        top1 = top1->next1;
        return(p1->data1);
        delete(p1);
    }
}
void push2(int data)
{
    np2 = new node2;
    np2->data2 = data;
    np2->next2 = NULL;
    if (top2 == NULL)
    {
        top2 = np2;
    }
    else
    {
        np2->next2 = top2;
        top2 = np2;
    }
}
int pop2()
{
    int b = 999;
    if (top2 == NULL)
    {
        return b;
    }
    else
    {
        p2 = top2;
        top2 = top2->next2;
        return(p2->data2);
        delete(p2);
    }
}
void push3(int data)
{
    np3 = new node3;
    np3->data3 = data;
    np3->next3 = NULL;
    if (top3 == NULL)
    {
        top3 = np3;
    }
    else
    {
        np3->next3 = top3;
        top3 = np3;
    }
}
int pop3()
{
    int b = 999;
    if (top3 == NULL)
    {
        return b;
    }
    else
    {
        p3 = top3;
        top3 = top3->next3;
        return(p3->data3);
        delete(p3);
    }
}
int top_of_stack()
{
    if (top1 != NULL && top1->data1 == 1 )
    {
        return 1;
    }
    else if (top2 != NULL && top2->data2 == 1)
    {
        return 2;
    }
    else if (top3 != NULL && top3->data3 == 1)
    {
        return 3;
    }
}
void display1()
{
    cout<<endl;
    node1 *p1;
    p1 = top1;
    cout<<"Tower1-> "<<"t";
    while (p1 != NULL)
    {
        cout<<p1->data1<<"t";
        p1 = p1->next1;
    }
    cout<<endl;
}
void display2()
{
    node2 *p2;
    p2 = top2;
    cout<<"Tower2-> "<<"t";
    while (p2 != NULL)
    {
        cout<<p2->data2<<"t";
        p2 = p2->next2;
    }
    cout<<endl;
}
void display3()
{
    node3 *p3;
    p3 = top3;
    cout<<"Tower3-> "<<"t";
    while (p3 != NULL)
    {
        cout<<p3->data3<<"t";
        p3 = p3->next3;
    }
    cout<<endl;
    cout<<endl;
}
void toh(int n)
{
    int i, x, a, b;
    for (i = 0; i < (pow(2,n)); i++)
    {
        display1();
        display2();
        display3();
        x = top_of_stack();
        if (i % 2 == 0)
        {
            if (x == 1)
            {
                push3(pop1());
            }
            else if (x == 2)
            {
                push1(pop2());
            }
            else if (x == 3)
            {
                push2(pop3());
            }
        }
        else
        {
            if (x == 1)
            {
                a = pop2();
                b = pop3();
                if (a < b && b != 999)
                {
                    push3(b);
                    push3(a);
                }
                else if (a > b && a != 999)
                {
                    push2(a);
                    push2(b);
                }
                else if (b == 999)
                {
                    push3(a);
                }
                else if (a == 999)
                {
                    push2(b);
                }
            }
            else if (x == 2)
            {
                a = pop1();
                b = pop3();
                if (a < b && b != 999)
                {
                    push3(b);
                    push3(a);
                }
                else if (a > b && a != 999)
                {
                    push1(a);
                    push1(b);
                }
                else if (b == 999)
                {
                    push3(a);
                }
                else if (a == 999)
                {
                    push1(b);
                }
            }
            else if (x == 3)
            {
                a = pop1();
                b = pop2();
                if (a < b && b != 999)
                {
                    push2(b);
                    push2(a);
                }
                else if (a > b && a != 999)
                {
                    push1(a);
                    push1(b);
                }
                else if (b == 999)
                {
                    push2(a);
                }
                else if (a == 999)
                {
                    push1(b);
                }
            }
        }
    }
}
int main()
{
    int n, i;
    cout<<"enter the number of disksn";
    cin>>n;
    for (i = n; i >= 1; i--)
    {
        push1(i);
    }
    toh(n);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

#include<stdio.h>

#include<iostream>

#include<math.h>

using namespace std;

struct node1

{

int data1;

node1 *next1;

}*top1 = NULL, *p1 = NULL, *np1 = NULL;

struct node2

{

int data2;

node2 *next2;

}*top2 = NULL, *p2 = NULL, *np2 = NULL;

struct node3

{

int data3;

node3 *next3;

}*top3 = NULL, *p3 = NULL, *np3 = NULL;

void push1(int data)

{

np1 = new node1;

np1->data1 = data;

np1->next1 = NULL;

if (top1 == NULL)

{

top1 = np1;

}

else

{

np1->next1 = top1;

top1 = np1;

}

int pop1()

{

int b = 999;

if (top1 == NULL)

{

return b;

}

else

{

p1 = top1;

top1 = top1->next1;

return(p1->data1);

delete(p1);

}

void push2(int data)

{

np2 = new node2;

np2->data2 = data;

np2->next2 = NULL;

if (top2 == NULL)

{

top2 = np2;

}

else

{

np2->next2 = top2;

top2 = np2;

}

int pop2()

{

int b = 999;

if (top2 == NULL)

{

return b;

}

else

{

p2 = top2;

top2 = top2->next2;

return(p2->data2);

delete(p2);

}

void push3(int data)

{

np3 = new node3;

np3->data3 = data;

np3->next3 = NULL;

if (top3 == NULL)

{

top3 = np3;

}

else

{

np3->next3 = top3;

top3 = np3;

}

int pop3()

{

int b = 999;

if (top3 == NULL)

{

return b;

}

else

{

p3 = top3;

top3 = top3->next3;

return(p3->data3);

delete(p3);

}

int top_of_stack()

{

if (top1 != NULL && top1->data1 == 1 )

{

return 1;

}

else if (top2 != NULL && top2->data2 == 1)

{

return 2;

}

else if (top3 != NULL && top3->data3 == 1)

{

return 3;

}

void display1()

{

cout<<endl;

node1 *p1;

p1 = top1;

cout<<"Tower1-> "<<"t";

while (p1 != NULL)

{

cout<<p1->data1<<"t";

p1 = p1->next1;

}

cout<<endl;

}

void display2()

{

node2 *p2;

p2 = top2;

cout<<"Tower2-> "<<"t";

while (p2 != NULL)

{

cout<<p2->data2<<"t";

p2 = p2->next2;

}

cout<<endl;

}

void display3()

{

node3 *p3;

p3 = top3;

cout<<"Tower3-> "<<"t";

while (p3 != NULL)

{

cout<<p3->data3<<"t";

p3 = p3->next3;

}

cout<<endl;

}

void toh(int n)

{

int i, x, a, b;

for (i = 0; i < (pow(2,n)); i++)

{

display1();

display2();

display3();

x = top_of_stack();

if (i % 2 == 0)

{

if (x == 1)

{

push3(pop1());

}

else if (x == 2)

{

push1(pop2());

}

else if (x == 3)

{

push2(pop3());

}

else

{

if (x == 1)

{

a = pop2();

b = pop3();

if (a < b && b != 999)

{

push3(b);

push3(a);

}

else if (a > b && a != 999)

{

push2(a);

push2(b);

}

else if (b == 999)

{

push3(a);

}

else if (a == 999)

{

push2(b);

}

else if (x == 2)

{

a = pop1();

b = pop3();

if (a < b && b != 999)

{

push3(b);

push3(a);

}

else if (a > b && a != 999)

{

push1(a);

push1(b);

}

else if (b == 999)

{

push3(a);

}

else if (a == 999)

{

push1(b);

}

else if (x == 3)

{

a = pop1();

b = pop2();

if (a < b && b != 999)

{

push2(b);

push2(a);

}

else if (a > b && a != 999)

{

push1(a);

push1(b);

}

else if (b == 999)

{

push2(a);

}

else if (a == 999)

{

push1(b);

}

int main()

{

int n, i;

cout<<"enter the number of disksn";

cin>>n;

for (i = n; i >= 1; i--)

{

push1(i);

}

toh(n);

return 0;

}

Sample Output:



enter the number of disks
5

Tower1->        1       2       3       4       5
Tower2->
Tower3->


Tower1->        2       3       4       5
Tower2->
Tower3->        1


Tower1->        3       4       5
Tower2->        2
Tower3->        1


Tower1->        3       4       5
Tower2->        1       2
Tower3->


Tower1->        4       5
Tower2->        1       2
Tower3->        3


Tower1->        1       4       5
Tower2->        2
Tower3->        3


Tower1->        1       4       5
Tower2->
Tower3->        2       3


Tower1->        4       5
Tower2->
Tower3->        1       2       3


Tower1->        5
Tower2->        4
Tower3->        1       2       3


Tower1->        5
Tower2->        1       4
Tower3->        2       3


Tower1->        2       5
Tower2->        1       4
Tower3->        3


Tower1->        1       2       5
Tower2->        4
Tower3->        3


Tower1->        1       2       5
Tower2->        3       4
Tower3->


Tower1->        2       5
Tower2->        3       4
Tower3->        1


Tower1->        5
Tower2->        2       3       4
Tower3->        1


Tower1->        5
Tower2->        1       2       3       4
Tower3->


Tower1->
Tower2->        1       2       3       4
Tower3->        5


Tower1->        1
Tower2->        2       3       4
Tower3->        5


Tower1->        1
Tower2->        3       4
Tower3->        2       5


Tower1->
Tower2->        3       4
Tower3->        1       2       5


Tower1->        3
Tower2->        4
Tower3->        1       2       5


Tower1->        3
Tower2->        1       4
Tower3->        2       5


Tower1->        2       3
Tower2->        1       4
Tower3->        5


Tower1->        1       2       3
Tower2->        4
Tower3->        5


Tower1->        1       2       3
Tower2->
Tower3->        4       5


Tower1->        2       3
Tower2->
Tower3->        1       4       5


Tower1->        3
Tower2->        2
Tower3->        1       4       5


Tower1->        3
Tower2->        1       2
Tower3->        4       5


Tower1->
Tower2->        1       2
Tower3->        3       4       5


Tower1->        1
Tower2->        2
Tower3->        3       4       5


Tower1->        1
Tower2->
Tower3->        2       3       4       5


Tower1->
Tower2->
Tower3->        1       2       3       4       5

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

enter the number of disks

Tower1-> 1 2 3 4 5

Tower2->

Tower3->

Tower1-> 2 3 4 5

Tower2->

Tower3-> 1

Tower1-> 3 4 5

Tower2-> 2

Tower3-> 1

Tower1-> 3 4 5

Tower2-> 1 2

Tower3->

Tower1-> 4 5

Tower2-> 1 2

Tower3-> 3

Tower1-> 1 4 5

Tower2-> 2

Tower3-> 3

Tower1-> 1 4 5

Tower2->

Tower3-> 2 3

Tower1-> 4 5

Tower2->

Tower3-> 1 2 3

Tower1-> 5

Tower2-> 4

Tower3-> 1 2 3

Tower1-> 5

Tower2-> 1 4

Tower3-> 2 3

Tower1-> 2 5

Tower2-> 1 4

Tower3-> 3

Tower1-> 1 2 5

Tower2-> 4

Tower3-> 3

Tower1-> 1 2 5

Tower2-> 3 4

Tower3->

Tower1-> 2 5

Tower2-> 3 4

Tower3-> 1

Tower1-> 5

Tower2-> 2 3 4

Tower3-> 1

Tower1-> 5

Tower2-> 1 2 3 4

Tower3->

Tower1->

Tower2-> 1 2 3 4

Tower3-> 5

Tower1-> 1

Tower2-> 2 3 4

Tower3-> 5

Tower1-> 1

Tower2-> 3 4

Tower3-> 2 5

Tower1->

Tower2-> 3 4

Tower3-> 1 2 5

Tower1-> 3

Tower2-> 4

Tower3-> 1 2 5

Tower1-> 3

Tower2-> 1 4

Tower3-> 2 5

Tower1-> 2 3

Tower2-> 1 4

Tower3-> 5

Tower1-> 1 2 3

Tower2-> 4

Tower3-> 5

Tower1-> 1 2 3

Tower2->

Tower3->