在一个特殊的家庭中找到职业

考虑一个特殊的工程师和医生家族,遵循以下规则:

null
  1. 每个人都有两个孩子。
  2. 工程师的第一个孩子是工程师,第二个孩子是医生。
  3. 医生的第一个孩子是医生,第二个孩子是工程师。
  4. 历代医生和工程师都是从工程师开始的。

我们可以用下图来表示情况:

                E           /                  E          D        /          /         E     D     D    E      /    /    /    /      E   D D   E  D  E  E  D

在上面的祖先树中给定一个人的等级和位置,找到此人的职业。 例如:

Input : level = 4, pos = 2Output : DoctorInput : level = 3, pos = 4Output : Engineer

方法1(递归) 这个想法基于这样一个事实:一个人的职业取决于以下两个方面。

  1. 父母的职业。
  2. 节点位置:如果节点的位置是奇数,则其职业与其父节点相同。否则,这个职业就不同于它的父母。

我们递归地找到父节点的职业,然后使用上面的第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' ):
print ( "Engineer" )
else :
print ( "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>


输出:

Doctor

方法2(使用位运算符)

Level 1: ELevel 2: EDLevel 3: EDDELevel 4: EDDEDEEDLevel 5: EDDEDEEDDEEDEDDE 

级别输入是不必要的(如果我们忽略最大位置限制),因为第一个元素是相同的。 结果基于位置-1的二进制表示中的1计数。如果1的计数为偶数,则结果为工程师,否则为医生。 当然,位置限制是2^(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);
}
}


Python3

# Python3 program to find profession of a person at
# given level and position.
""" Function to get no of set bits in binary
representation of passed binary no. """
def countSetBits(n):
count = 0
while n > 0 :
n & = (n - 1 )
count + = 1
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.
def findProffesion(level, pos):
# Count set bits in 'pos-1'
c = countSetBits(pos - 1 )
# If set bit count is odd, then doctor, else engineer
if c % 2 = = 0 :
return 'e'
else :
return 'd'
level, pos = 3 , 4
if findProffesion(level, pos) = = 'e' :
print ( "Engineer" )
else :
print ( "Doctor" )
# This code is contributed by divyeshrabadiya07.


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.
// Function to get no of set
// bits in binary representation
// of passed binary no.
function countSetBits( $n )
{
$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.
function findProffesion( $level , $pos )
{
// Count set bits in 'pos-1'
$c = countSetBits( $pos - 1);
// If set bit count is odd,
// then doctor, else engineer
return ( $c % 2) ? 'd' : 'e' ;
}
// Driver Code
$level = 3;
$pos = 4;
if ((findProffesion( $level ,
$pos ) == 'e' ) == true)
echo "Engineer " ;
else
echo "Doctor " ;
// This code is contributed by aj_36
?>


Javascript

<script>
// Javascript program to find
// profession of a person at
// given level and position.
/* Function to get no of set bits in binary
representation of passed binary no. */
function countSetBits(n)
{
let 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.
function findProffesion(level, pos)
{
// Count set bits in 'pos-1'
let c = countSetBits(pos - 1);
// If set bit count is odd, then doctor,
// else engineer
return (c % 2 != 0)? 'd' : 'e' ;
}
let level = 3, pos = 4;
let prof = (findProffesion(level, pos) == 'e' )?
"Engineer" : "Doctor" ;
document.write(prof);
</script>


输出:

Engineer

感谢Furkan Uslu提出的这种方法。 本文由 苛刻的贱民 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。

© 版权声明
THE END
喜欢就支持一下吧
点赞7 分享