Найдите профессию в особенной семье
Рассмотрим особую семью инженеров и врачей со следующими правилами:
- У всех двое детей.
- Первый ребенок инженера - инженер, а второй ребенок - доктор.
- Первый ребенок Доктора - Доктор, а второй ребенок - Инженер.
- Все поколения врачей и инженеров начинаются с инженера.
Мы можем представить ситуацию, используя диаграмму ниже:
E / ED / / EDDE / / / / EDDEDEED
Зная уровень и положение человека в верхнем дереве предков, найдите профессию человека.
Примеры :
Ввод: уровень = 4, поз = 2 Выход: Доктор Ввод: уровень = 3, поз = 4 Продукт: Инженер
Метод 1 (рекурсивный)
Идея основана на том, что профессия человека зависит от следующих двух.
- Профессия родителя.
- Положение узла: если положение узла нечетное, то его профессия такая же, как у его родителя. Другая профессия отличается от своей родительской.
Мы рекурсивно находим профессию родителя, затем используем пункт 2 выше, чтобы найти профессию текущего узла.
Ниже представлена реализация вышеизложенной идеи.
C++
// C++ program to find profession of a person at
// given level and position.
#include<bits/stdc++.h>
using
namespace
std;
// Returns "e" if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level == 1)
return
"e"
;
// Recursively find parent"s profession. If parent
// is a Doctor, this node will be a Doctor if it is
// at odd position and an engineer if at even position
if
(findProffesion(level-1, (pos+1)/2) ==
"d"
)
return
(pos%2)?
"d"
:
"e"
;
// If parent is an engineer, then current node will be
// an engineer if at add position and doctor if even
// position.
return
(pos%2)?
"e"
:
"d"
;
}
// Driver code
int
main(
void
)
{
int
level = 4, pos = 2;
(findProffesion(level, pos) ==
"e"
)? cout <<
"Engineer"
: cout <<
"Doctor"
;
return
0;
}
Java
// Java program to find
// profession of a person
// at given level and position
import
java.io.*;
class
GFG
{
// Returns "e" if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level ==
1
)
return
"e"
;
// Recursively find parent"s
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level -
1
,
(pos +
1
) /
2
) ==
"d"
)
return
(pos %
2
>
0
) ?
"d"
:
"e"
;
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return
(pos %
2
>
0
) ?
"e"
:
"d"
;
}
// Driver code
public
static
void
main (String[] args)
{
int
level =
4
, pos =
2
;
if
(findProffesion(level,
pos) ==
"e"
)
System.out.println(
"Engineer"
);
else
System.out.println(
"Doctor"
);
}
}
// This code is contributed
// by anuj_67.
Python3
# python 3 program to find profession of a person at
# given level and position.
# Returns "e" if profession of node at given level
# and position is engineer. Else doctor. The function
# assumes that given position and level have valid values.
def
findProffesion(level, pos):
# Base case
if
(level
=
=
1
):
return
"e"
# Recursively find parent"s profession. If parent
# is a Doctor, this node will be a Doctor if it is
# at odd position and an engineer if at even position
if
(findProffesion(level
-
1
, (pos
+
1
)
/
/
2
)
=
=
"d"
):
if
(pos
%
2
):
return
"d"
else
:
return
"e"
# If parent is an engineer, then current node will be
# an engineer if at add position and doctor if even
# position.
if
(pos
%
2
):
return
"e"
else
:
return
"d"
# Driver code
if
__name__
=
=
"__main__"
:
level
=
3
pos
=
4
if
(findProffesion(level, pos)
=
=
"e"
):
(
"Engineer"
)
else
:
(
"Doctor"
)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find
// profession of a person
// at given level and position
using
System;
class
GFG
{
// Returns "e" if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level == 1)
return
"e"
;
// Recursively find parent"s
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level - 1,
(pos + 1) / 2) ==
"d"
)
return
(pos % 2 > 0) ?
"d"
:
"e"
;
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return
(pos % 2 > 0) ?
"e"
:
"d"
;
}
// Driver code
public
static
void
Main ()
{
int
level = 4, pos = 2;
if
(findProffesion(level,
pos) ==
"e"
)
Console.WriteLine(
"Engineer"
);
else
Console.WriteLine(
"Doctor"
);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find profession
// of a person at given level
// and position.
// Returns "e" if profession of
// node at given level and position
// is engineer. Else doctor. The
// function assumes that given
// position and level have valid values.
function
findProffesion(
$level
,
$pos
)
{
// Base case
if
(
$level
== 1)
return
"e"
;
// Recursively find parent"s
// profession. If parent is
// a Doctor, this node will
// be a doctor if it is at
// odd position and an engineer
// if at even position
if
(findProffesion(
$level
- 1,
(
$pos
+ 1) / 2) ==
"d"
)
return
(
$pos
% 2) ?
"d"
:
"e"
;
// If parent is an engineer, then
// current node will be an engineer
// if at odd position and doctor
// if even position.
return
(
$pos
% 2) ?
"e"
:
"d"
;
}
// Driver code
$level
= 4;
$pos
= 2;
if
((findProffesion(
$level
,
$pos
) ==
"e"
) == true)
echo
"Engineer"
;
else
echo
"Doctor"
;
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find
// profession of a person
// at given level and position
// Returns "e" if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
function
findProffesion(level,
pos)
{
// Base case
if
(level == 1)
return
"e"
;
// Recursively find parent"s
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level - 1,
(pos + 1) / 2) == "d
")
return (pos % 2 > 0) ?
"
d
" : "
e
";
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return (pos % 2 > 0) ?
"
e
" : "
d
";
}
// Driver Code
let level = 4, pos = 2;
if(findProffesion(level,
pos) == "
e")
document.write(
"Engineer"
);
else
document.write(
"Doctor"
);
</script>
Выход :
Доктор
Метод 2 (с использованием побитовых операторов)
Уровень 1: E Уровень 2: ED Уровень 3: EDDE Уровень 4: EDDEDEED Уровень 5: EDDEDEEDDEEDEDDE
Level input isn’t necessary (if we ignore max position limit) because first elements are same.
The result is based on count of 1’s in binary representation of position minus one. If count of 1’s is even then result is Engineer, else then Doctor.
And of course position limit is 2^(Level-1)
C++
// C++ program to find profession of a person at // given level and position. #include<bits/stdc++.h> using namespace std; /* Function to get no of set bits in binary representation of passed binary no. */ int countSetBits( int n) { int count = 0; while (n) { n &= (n-1) ; count++; } return count; } // Returns "e" if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. char findProffesion( int level, int pos) { // Count set bits in "pos-1" int c = countSetBits(pos-1); // If set bit count is odd, then doctor, else engineer return (c%2)? "d" : "e" ; } // Driver code int main( void ) { int level = 3, pos = 4; (findProffesion(level, pos) == "e" )? cout << "Engineer" : cout << "Doctor" ; return 0; } |
Java
// Java program to find profession of a person at // given level and position. class GFG{ /* Function to get no of set bits in binary representation of passed binary no. */ static int countSetBits( int n) { int count = 0 ; while (n!= 0 ) { n &= (n- 1 ) ; count++; } return count; } // Returns "e" if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. static char findProffesion( int level, int pos) { // Count set bits in "pos-1" int c = countSetBits(pos- 1 ); // If set bit count is odd, then doctor, else engineer return (c% 2 != 0 )? "d" : "e" ; } // Driver code public static void main(String [] args) { int level = 3 , pos = 4 ; String prof = (findProffesion(level, pos) == "e" )? "Engineer" : "Doctor" ; System.out.print(prof); } } |
C#
using System; // c# program to find profession of a person at // given level and position. public class GFG { /* Function to get no of set bits in binary representation of passed binary no. */ public static int countSetBits( int n) { int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; } // Returns "e" if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. public static char findProffesion( int level, int pos) { // Count set bits in "pos-1" int c = countSetBits(pos - 1); // If set bit count is odd, then doctor, else engineer return (c % 2 != 0)? "d" : "e" ; } // Driver code public static void Main( string [] args) { int level = 3, pos = 4; string prof = (findProffesion(level, pos) == "e" )? "Engineer" : "Doctor" ; Console.Write(prof); } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to find profession // of a person at given level and position. РЕКОМЕНДУЕМЫЕ СТАТЬИ |